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. 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.

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.

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. 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.

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.

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

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

• Sablon:Fordítás

További információk

• Sablon:OEIS: Konvex rétegek száma egy n×n-es rácsban