Voronoj-cella

A Wikipédiából, a szabad enciklopédiából
A Voronoj-cella egy ábrázolása véletlenszerűen elhelyezkedő pontok esetén.

A Voronoj-cella egy matematikai transzformáció eredménye. Egy ponthalmaz egy elemének Voronoj-cellája azokat a síkbeli, vagy térbeli pontokat tartalmazza, amikhez az adott ponthalmazból az adott pont van a legközelebb. Nevét Georgij Voronoj ukrán matematikusról kapta. A síkon egy véletlenszerűen elhelyezkedő pontrácsozathoz úgy tudjuk hozzárendelni a Voronoj-cellákat, hogy meghúzzuk a szomszédos pontok közötti felezőket és az így kapott szakaszokat, mint a pontok körül tartományt kirajzoló cellaéleket tekintjük. 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 transzformáció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 sokszögek a síkban, vagy konvex poliéderek a térben. A diagram mérete lineáris a pontok számára nézve. A ponthalmaz egy pontjának akkor és csak akkor végtelen a Voronoj-cellája, ha a konvex burok határára esik.

A Dirichlet-Voronoj-cellákat kialakító transzformációra a levélállás bemutatásánál láthatunk példát.

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

Algoritmus[szerkesztés | forrásszöveg szerkesztése]

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 P1, P, …, Pn a megadott ponthalmaz pontjait. 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 P1, P, …, Pn 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.

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.[1]

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

  1. S. Arya, T. Malamatos, és David Mount, Space-Efficient Voronoj-diagramok approximációja, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721–730.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Fortune-algoritmus

Külső hivatkozás[szerkesztés | forrásszöveg szerkesztése]