Konvex rétegek

A matematika, azon belül a számítási geometria területén az euklideszi síkon lévő ponthalmaz konvex rétegei (convex layers) alatt a halmaz pontjait csúcsként tartalmazó, egymásba ágyazott konvex sokszögek sorozata értendő. A legkülső réteg a pontok konvex burkával egyezik meg, a többi réteget a megmaradó pontokból rekurzív módon képezik. A legbelső réteg degenerált, egy vagy két pontból álló is lehet.^[1] A konvex rétegek előállításának problémáját „hagymahámozásnak” (onion peeling) vagy „hagymafelbontásnak” (onion decomposition) is nevezik.^[2]

Bár a konvex rétegek előállíthatók a konvex burok rekurzív képzésével is, az $n$ pontból álló halmaz konvex rétegekre bontására ennél lényegesen gyorsabb, $O(n\log n)$ idejű algoritmus is létezik.^[1]

A konvex rétegek egyik első felhasználási területe a robusztus statisztika területén a kiugró értékek azonosítása és a mintapontok egy halmaza centrális tendenciájának mérése volt.^[3]^[4] Ebben a kontextusban egy adott pontot körülvevő konvex rétegek számát a pont „konvexburok-hámozási mélységének” (convex hull peeling depth) nevezik, maguk a konvex rétegek pedig az adatmélység itt értelmezett fogalma szerinti mélységvonalakat (depth contours) alkotják.^[5]

A konvex rétegek felhasználhatók egy lekérdező félsík összes pontjának hatékony, tartományriport (range reporting, egy adott mértani objektumon belüli pontok megkeresése) céljára szolgáló adatstruktúrájában. Az egymást követő rétegek a félsíkon belül eső pontjait a félsík irányában lévő legszélső helyzetű pontból kiinduló bináris kereséssel lehet megtalálni. Az egymást követő bináris keresések fractional cascading algoritmussal felgyorsíthatók, így a teljes lekérdezési idő $O(\log n+k)$ , amennyiben $k$ pontot találunk meg egy $n$ elemű halmazból.^[6]

Az $n\times n$ négyzetrács $\Theta (n^{4/3})$ konvex réteggel rendelkezik,^[7] ami tetszőleges, konvex alakzatban egyenletes eloszlás szerint elhelyezkedő pontokra is igaz.^[8]

A konvex rétegek előállítása magasabb dimenziókban is hasonlóan történhet, de elsősorban a 2 dimenziós esetnek ismertek gyakorlati alkalmazásai.

Fordítás

Ez a szócikk részben vagy egészben a Convex layers című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

(A290966 sorozat az OEIS-ben): Konvex rétegek száma egy n×n-es rácsban

Jegyzetek

↑ ^a ^b Chazelle, Bernard (1985), "On the convex layers of a planar set", IEEE Trans. Inform. Theory 31 (4): 509–517, DOI 10.1109/TIT.1985.1057060
↑ Löffler, Maarten & Mulzer, Wolfgang (2014), "Unions of onions: preprocessing imprecise points for fast onion decomposition", Journal of Computational Geometry 5 (1): 1–13, DOI 10.20382/jocg.v5i1a1.
↑ Barnett, V. (1976), "The ordering of multivariate data", J. Roy. Statist. Soc. Ser. A 139 (3): 318–355, DOI 10.2307/2344839
↑ Eddy, W. F. (1982), "Convex Hull Peeling", COMPSTAT 1982 5th Symposium held at Toulouse 1982, Physica-Verlag, pp. 42–47, DOI 10.1007/978-3-642-51461-6_4
↑ Liu, Regina Y.; Parelius, Jesse M. & Singh, Kesar (1999), "Multivariate analysis by data depth: descriptive statistics, graphics and inference", Annals of Statistics 27 (3): 783–858, DOI 10.1214/aos/1018031260
↑ Chazelle, Bernard; Guibas, Leo J. & Lee, D. T. (1985), "The power of geometric duality", BIT 25 (1): 76–90, DOI 10.1007/BF01934990
↑ Har-Peled, Sariel & Lidický, Bernard (2013), "Peeling the grid", SIAM Journal on Discrete Mathematics 27 (2): 650–655, DOI 10.1137/120892660
↑ Dalal, Ketan (2004), "Counting the onion", Random Structures & Algorithms 24 (2): 155–165, DOI 10.1002/rsa.10114

[c85-1] Chazelle, Bernard (1985), "On the convex layers of a planar set", IEEE Trans. Inform. Theory 31 (4): 509–517, DOI 10.1109/TIT.1985.1057060

[2] Löffler, Maarten & Mulzer, Wolfgang (2014), "Unions of onions: preprocessing imprecise points for fast onion decomposition", Journal of Computational Geometry 5 (1): 1–13, DOI 10.20382/jocg.v5i1a1.

[3] Barnett, V. (1976), "The ordering of multivariate data", J. Roy. Statist. Soc. Ser. A 139 (3): 318–355, DOI 10.2307/2344839

[4] Eddy, W. F. (1982), "Convex Hull Peeling", COMPSTAT 1982 5th Symposium held at Toulouse 1982, Physica-Verlag, pp. 42–47, DOI 10.1007/978-3-642-51461-6_4

[5] Liu, Regina Y.; Parelius, Jesse M. & Singh, Kesar (1999), "Multivariate analysis by data depth: descriptive statistics, graphics and inference", Annals of Statistics 27 (3): 783–858, DOI 10.1214/aos/1018031260

[6] Chazelle, Bernard; Guibas, Leo J. & Lee, D. T. (1985), "The power of geometric duality", BIT 25 (1): 76–90, DOI 10.1007/BF01934990

[7] Har-Peled, Sariel & Lidický, Bernard (2013), "Peeling the grid", SIAM Journal on Discrete Mathematics 27 (2): 650–655, DOI 10.1137/120892660

[8] Dalal, Ketan (2004), "Counting the onion", Random Structures & Algorithms 24 (2): 155–165, DOI 10.1002/rsa.10114

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]