Voronoj-cella
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.
Tartalomjegyzék |
Algoritmus [szerkesztés]
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 
konstansszorosa.
Magasabb dimenzióban a Voronoj-cellák tárolására szolgáló adatstruktúra mérete 
. Ezért sokszor inkább approximálják őket.[1]
Alkalmazások [szerkesztés]
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]
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 euklidészi 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-diagrammok is, ahol is a távolságfüggvény kap additív vagy multiplikatív súlyozást.
Források [szerkesztés]
- ↑ S. Arya, T. Malamatos, és David Mount, Space-Efficient Voronoj-diagrammok approximációja, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721–730.
- Coxeter: A geometriák alapjai, Műszaki Kiadó, Budapest, 1973
- Elekes György: Kombinatorikus algoritmusok
- Térinformatikai alkalmazás
- Linkgyűjtemény más alkalmazásokkal
