Voronoj-cella
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 német 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,[1] 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ó
szerkesztésLegyen egy X metrikus térben d a távolságfüggvény, és legyen a K egy indexhalmaz. A halmaz minden eleme legyen X-beli, azaz -ra . Ekkor -ra a -hoz tartozó Voronoj-cella a következő:
- .
Egyszerű következmények
szerkesztés- Ha van két azonos pont a kiindulási ponthalmazban, azaz valamely és indexpárra, akkor .
- Egyetlen P1 pontból álló kiindulási ponthalmaz Voronoj-cellája a teljes X.
Algoritmus
szerkesztésA 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 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 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.
Másik algoritmus ugyanerre a Fortune-algoritmus.
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.[2]
Alkalmazások
szerkesztésA 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ésA 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.
Jegyzetek
szerkesztés- ↑ A Voronoj-cellák azért konvexek, mert konvex halmazok (félsíkok és félterek) metszeteiként állnak elő. Síkban n darab különböző pont esetén egy P1 pont Voronoj-cellájába azok a pontok tartoznak, amelyek a P1 és P2 közötti felező merőleges által kettévágott sík P1-et tartalmazó részében vannak, valamint a P1 és P3 közötti felező merőleges által kettévágott sík P1-et tartalmazó részében vannak, valamint stb. ugyanígy Pn-ig. Az n–1 darab konvex félsík közös része a metszetük, ami szintén konvex lesz, tehát a P1 Voronoj-cellája konvex. Hasonlóan belátható ugyanez a többi pontra is. A térbeli eset is hasonlóan belátható.
- ↑ 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.
Források
szerkesztés- 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