Delaunay-háromszögelés forrásának megtekintése

[[Fájl:Delaunay_circumcircles_vectorial.svg|right|thumb|280px|Delaunay-háromszögelés a síkban az üreskörök jelzésével]]
A [[geometria|geometriában]] és a [[számítástudomány]]ban 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ög]]ek, 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.<ref>Delaunay, Boris N.: Sur la sphère vide. In: ''Bulletin of Academy of Sciences of the USSR'' 7 (1934), Nr.&nbsp;6, S.&nbsp;793-800</ref> 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''<sub>1</sub>, ''P'', …, ''P''<sub>''n''</sub> a megadott ponthalmaz pontjait. Felvetítjük ezeket a pontokat arra a paraboloidra, aminek egyenlete ''x''<sup>2</sup> + ''y''<sup>2</sup> = ''z'', és meghatározzuk az alsó rész konvex burkát. Ez megadja a ''P''<sub>1</sub>, ''P'', …, ''P''<sub>''n''</sub> pontok Delaunay-háromszögelését.

Ez az [[algoritmus]] magasabb dimenzióra is általánosítható, ahol legfeljebb <math>O(n^{\lceil d/2 \rceil})</math> 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 <math>n \log n</math> konstansszorosa.

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

Adva legyenek a sík ''P''<sub>1</sub>, … , ''P''<sub>n</sub> pontjai. Keresünk ehhez Delaunay-háromszögelést.

Elsőként felveszünk még három pontot úgy, hogy a ''P''<sub>1</sub>, … , ''P''<sub>n</sub> 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''<sub>r</sub> pontot, és keresünk egy ''P''<sub>i</sub>''P''<sub>j</sub>''P''<sub>k</sub> háromszöget, ami tartalmazza. Beszúrjuk a ''P''<sub>r</sub> pontot a ''P''<sub>r</sub>''P''<sub>i</sub>, ''P''<sub>r</sub>''P''<sub>j</sub>, ''P''<sub>r</sub>''P''<sub>k</sub> élekkel, de figyelni kell, hogy nem lett-e a ''P''<sub>i</sub>''P''<sub>j</sub>''P''<sub>k</sub> 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''<sub>r</sub> két már létező háromszög határára, a ''P''<sub>i</sub>''P''<sub>j</sub> é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 [[geoinformatika|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ódszer]]ben 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.

== Jegyzetek ==
{{jegyzetek}}
* Elekes György: Kombinatorikus geometriai algoritmusok
* [https://web.archive.org/web/20160304131217/http://geometria.3x.ro/programok/delaunay/delaunay.htm Térinformatikai alkalmazás]
* [http://www.ics.uci.edu/~eppstein/gina/delaunay.html Linkgyűjtemény más alkalmazásokkal]

[[Kategória:Diszkrét geometria]]