![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/db/Delaunay_circumcircles_vectorial.svg/langhu-640px-Delaunay_circumcircles_vectorial.svg.png&w=640&q=50)
Delaunay-háromszögelés
From Wikipedia, the free encyclopedia
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.[1] Tartalmazza a legközelebbi szomszédok gráfját, és a P ponthalmaz euklideszi minimális feszítőfáit.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/db/Delaunay_circumcircles_vectorial.svg/320px-Delaunay_circumcircles_vectorial.svg.png)