Konvex rétegek

Egy ponthalmaz konvex rétegei és félsíkkal való metszetük

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 ${\displaystyle n}$ pontból álló halmaz konvex rétegekre bontására ennél lényegesen gyorsabb, ${\displaystyle 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ő ${\displaystyle O(\log n+k)}$, amennyiben ${\displaystyle k}$ pontot találunk meg egy ${\displaystyle n}$ elemű halmazból.[6]

Az ${\displaystyle n\times n}$ négyzetrács ${\displaystyle \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

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