Delaunay-háromszögelés

Delaunay-háromszögelés a síkban az üreskörök jelzésével

A geometriában és a számítástudományban egy adott P ponthalmaz Delaunay-háromszögelése egy olyan egyenes szakaszokból álló vonalhálózat, aminek sokszögtartományai köré írt gömbjei csak határukon tartalmazzák a P ponthalmaz pontjait. A korlátos sokszögtartományok tehát húrsokszögek. Ha ezek a tartományok nem mind háromszögek, akkor a Delaunay-háromszögelés elfajuló, egyébként valódi. A Delaunay-háromszögelés akkor és csak akkor valódi, ha a P halmaz pontjai között semelyik három nincs egy egyenesen, és semelyik négy nincs egy körön. Az élek száma lineárisan függ a pontok számától. A P ponthalmaz valódi Delaunay-háromszögelésének fontos tulajdonsága, hogy a P halmaz összes háromszögelése között maximalizálja a háromszögek legkisebb szögét. A Voronoj-diagram duálisa. Ezt a háromszögelést Borisz Nyikolajevics Döloné, franciásan Boris Delaunay vezette be 1934-ben. Tartalmazza a legközelebbi szomszédok gráfját, és a P ponthalmaz euklideszi minimális feszítőfáit.

Algoritmus

A háromszögelés elkészítésének egy módja, hogy kilépünk az eggyel magasabb dimenzióba.

Jelölje P₁, P, …, P_n a megadott ponthalmaz pontjait. Felvetítjük ezeket a pontokat arra a paraboloidra, aminek egyenlete x² + y² = z, és meghatározzuk az alsó rész konvex burkát. Ez megadja a P₁, P, …, P_n pontok Delaunay-háromszögelését.

Ez az algoritmus magasabb dimenzióra is általánosítható, ahol legfeljebb $O(n^{\lceil d/2\rceil })$ tartományra kell számítani. Itt a felbontás üresgömb-felbontást ad. A valódiság szükséges és elégséges feltétele, hogy a pontok általános helyzetűek legyenek: ne legyen d + 1 pont egy hipersíkban, és d + 2 pont egy hipergömbön.

Az itt leírt algoritmus ideje $n\log n$ konstansszorosa.

A háromszögelés a síkban maradva is megkapható.

Adva legyenek a sík P₁, … , P_n pontjai. Keresünk ehhez Delaunay-háromszögelést.

Elsőként felveszünk még három pontot úgy, hogy a P₁, … , P_n pontok az ezek által alkotott háromszög belsejében legyenek. Ez a háromszög lesz a kiindulási háromszögelés, ezt finomítjuk a későbbiekben. A végén ezek a pontok a belőlük induló élekkel együtt törölhetők.

A finomításhoz választunk egy új P_r pontot, és keresünk egy P_iP_jP_k háromszöget, ami tartalmazza. Beszúrjuk a P_r pontot a P_rP_i, P_rP_j, P_rP_k élekkel, de figyelni kell, hogy nem lett-e a P_iP_jP_k háromszög valamelyik éle szabálytalan. A háromszögelés egy éle szabálytalan, ha elrontja az üres kör tulajdonságot. Az ilyen élt törölni kell, és az így keletkező négyszög másik átlóját kell behúzni. Ezt mindaddig ismételni kell, amíg van az üres kör tulajdonságot elrontó él a háromszögelésben. Ha P_r két már létező háromszög határára, a P_iP_j élre esik, akkor mind a két háromszöget figyelembe kell venni. Be kell kötni az új éleket, és a régi éleket meg kell vizsgálni, és szükség esetén cserélni mindaddig, amíg van szabálytalan él.

Alkalmazások

A Delaunay-háromszögelést sok helyen használják, mert kerüli a nagyon keskeny, vékony háromszögeket. A térinformatikában négyszögháló helyett a mérési pontokra illesztett Delaunay-háromszögelést alkalmazzák az adatok jobb megőrzésének érdekében. Ennek segítségével a felszín könnyen háromszögelhető, ami megkönnyíti az elemző függvények alkalmazását, így az esésviszonyok, benapolás, kitettség valósághű elemzését. A háromszögvonalakkal közelíthetők a szintvonalak, számítható a felszíndarabok területe és a kiemelkedések térfogata.

A végeselemes módszerben is használják a Delaunay-háromszögelést, mert kerüli a keskeny háromszögeket, és azért, mert könnyen konstruálható. A numerikus stabilitás érdekében további finomításra van szükség.

Ezen kívül még számos más alkalmazással bír, így a kristálynövekedésben, a szívritmuszavarok osztályozásában, és a fehérjék szerkezetének elemzésében.

Források

• Elekes György: Kombinatorikus geometriai algoritmusok
• Térinformatikai alkalmazás
• Linkgyűjtemény más alkalmazásokkal