Voronoj-cella

Egy síkbeli ponthalmaz Voronoj-diagramja

A Voronoj-cella egy geometriai fogalom, nevét Georgij Voronoj ukrán matematikusról kapta. Egy ponthalmaz egy elemének Voronoj-cellája azokat a síkbeli – illetve térbeli – pontokat tartalmazza, amikhez a ponthalmazból az adott elem van a legközelebb. A síkon egy pont Voronoj-celláját a ponthalmaz többi elemével vett felező merőlegesek által határolt tartományként kaphatjuk meg, térben pedig a felező merőleges síkok által határolt konvex tartományként. (A határoló pontok egyszerre kettő vagy több cellához tartoznak.) Ilyen cellaképzést Dirichlet francia matematikus is készített, ezért gyakran nevezik az így kapott cellákat Dirichlet–Voronoj-celláknak is.

Érdemes megjegyezni, hogy szabályos pontrács esetén a pontrácsot szabályos cella-mozaikrácsba viszi át a Dirichlet–Voronoj-cellaképzés művelete. A lapközepes kockarács pontjainak Voronoj-cellája rombododekaéder, a térközepes kockarácséinak csonkított oktaéder. A pontrács pontjait összekötve ilyenkor a szabályos cella-mozaikrács duálisát kapjuk meg.

A Voronoj-cellák konvex zárt halmazok, de nem feltétlenül korlátosak. Korlátos esetben a síkban konvex sokszögek, a térben konvex poliéderek, korlátlan esetben a síkban végtelenbe nyúló, félegyenesekkel és szakaszokkal határolt konvex síkrészek, a térben pedig végtelenbe nyúló, végtelen síkdarabokkal és konvex poliéderekkel határolt konvex térrészek. A ponthalmaz egy pontjának akkor és csak akkor végtelen a Voronoj-cellája, ha a pont a ponthalmaz konvex burkának a határára esik.

Voronoj-cellák nem csak síkban vagy térben értelmezhetőek, hanem például egy gömb vagy a Föld felszínén is.

A Voronoj-diagram mérete lineáris a pontok számára nézve.

A Voronoj-diagram duálisa a Delaunay-háromszögelés.

Formális definíció

Legyen egy X metrikus térben d a távolságfüggvény, és legyen a K egy indexhalmaz. A $\scriptstyle \{P_{k}\}_{k\in K}$ halmaz minden eleme legyen X-beli, azaz $\scriptstyle \forall k\in K$-ra $\scriptstyle P_{k}\in X$. Ekkor $\scriptstyle \forall k\in K$-ra a $\scriptstyle P_{k}$-hoz tartozó $\scriptstyle R_{k}$ Voronoj-cella a következő:

$R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{minden}}\;j\in K,\ j\neq k\ {\text{esetében}}\ \}$.

Egyszerű következmények

• Ha van két azonos pont a kiindulási ponthalmazban, azaz $\scriptstyle P_{i}=P_{j}$ valamely $\scriptstyle i,j\in K$ és $\scriptstyle i\neq j$ indexpárra, akkor $\scriptstyle R_{i}=R_{j}$.
• Egyetlen P₁ pontból álló kiindulási ponthalmaz Voronoj-cellája a teljes X.

Algoritmus

A bevezetőben vázolt módszer egyszerű, de lassú. Gyorsabb algoritmust kapunk, ha kilépünk a térbe, azaz egy magasabb dimenzióba.

Jelölje {P₁, P, …, P_n} a megadott ponthalmazt. Felvetítjük ezeket a pontokat arra a paraboloidra, aminek egyenlete x² + y² = z, és ezekben a pontokban meghatározzuk a parabola érintősíkjait. A síkok fölötti félterek metszetét levetítjük a síkra. Ez megadja a P₁, P, …, P_n pontok Voronoi-celláit.

Ez az algoritmus magasabb dimenzióra is általánosítható.

A bevezetőben szereplő algoritmus ideje egyenesen arányos a pontok számának harmadik hatványával. Az itt leírt algoritmus ennél sokkal gyorsabb: ideje $n\log n$ konstansszorosa.

Másik algoritmus ugyanerre a Fortune-algoritmus.

Magasabb dimenzióban a Voronoj-cellák tárolására szolgáló adatstruktúra mérete $O(n^{\lceil d/2\rceil })$. Ezért sokszor inkább approximálják őket.

Alkalmazások

A Voronoj-cellák egy fontos alkalmazási területe a térinformatikai rendszerek. Velük modellezhető például a csapadék eloszlása.

A magasabb dimenziós Voronoj-cellákkal több tulajdonság is geometriai módszerekkel modellezhető: k dimenziós Voronoj-cellákkal k-3 tulajdonság kezelhető, mint például hőmérséklet, koncentráció és sűrűség. Ezzel lehetővé válik, hogy az adattárolást és -kezelést geometriai módszerekkel végezzék.

A térinformatikai rendszerekben súlyozott Voronoj-cellákkal is kísérleteznek.

A Voronoj-celláknak más alkalmazásaik is vannak, például a biometriában, felületek felosztásában, a dokumentumanalízisben, és a kristálytanban.

Általánosítások

A k-adrendű Voronoj-cellák azokat a pontokat tartalmazzák, amikhez ezek a pontok vannak a legközelebb. Ez szintén felosztja a teret. Konstrukciójuk a forgásparaboloidot használó algoritmushoz hasonlóan, az érintősíkok k-adik szintjén levő metszésvonalai mentén.

Voronoj-cellák definiálhatók a nem euklideszi metrikát használó terekben is. Ekkor nem biztos, hogy felosztást kapunk, mert nem biztos, hogy a szakaszfelezők hipersíkok lesznek. Hasonlóan kaphatók a súlyozott Voronoj-diagramok is, ahol is a távolságfüggvény kap additív vagy multiplikatív súlyozást.

Források

• H. S. M. Coxeter: A geometriák alapjai (Műszaki, 1973)
• Elekes György: Kombinatorikus algoritmusok (egyetemi jegyzet)
• Térinformatikai alkalmazás
• Linkgyűjtemény más alkalmazásokkal

Külső hivatkozások

• Fortune-algoritmus PDF