Delaunay triangulatsioon
Delaunay triangulatsioon (hääldus: delo'nee) on matemaatika ja arvutusgeomeetria mõiste. See on defineeritud kui punktihulga P triangulatsioon pinnal nii, et moodustatavate kolmnurkade sees ei oleks ühtegi punkti ning kolmnurkade tipud ühtivad punktidega. Delaunay triangulatsioon on nimetatud nõukogude teadlase Boriss Delaunay järgi, kes tegeles selle teemaga alates 1934. aastast. Delaunay triangulatsioon maksimeerib kolmnurkade väikseima nurga, mille läbi välditakse liiga kitsaid kolmnurki. Delaunay triangulatsiooni ei ole samal sirgel asuvate punktide jaoks. Kui punkti ümber kujutletud ringjoonel on 4 või rohkem punkti (näiteks ringi sisse kujuteldava ruudu diagonaalidel), pole Dealunay triangulatsioon enam üheselt määratud. Sel juhul rahuldavad mõlemad võimalikud triangulatsioonid Delaunay tingimust: tekivad kolmnurgad, mille sisemused jäävad tühjaks. Võttes arvesse punkte ühendavad ringjooned, saab Delaunay triangulatsiooni defineerida ka kolme- ja enamamõõtmelistele punktihulkadele. Üldistused on võimalikud ka väljapoole eukleidilisi ruume. Sellistel juhtudel on aga võimalik, et Delaunay triangulatsiooni ei eksisteeri või ei ole see ühene. Kuna lõplike elementide meetod (inglise keeles finit element method) ja piirielementide meetod (boundary element method) muutuvad järjest populaarsemaks, kasvab põhjus arendada automaatseid võrestiku moodustamise meetodeid. Vaatamata paljudele võrestiku moodustamise meetoditele, on võimalik, et nende abil loodud võrestikud tulevad moondunud ja kasutamatud. Selle probleemi lahenduseks on olemas meetodid, mille abil olemasolevat võret parandada. Näiteks võib tuua silumise, mille käigus kontrollitakse üle punkti kuuluvus kolmnurkadesse ja vajadusel muudetakse seda. Seeläbi väheneb võrestiku moone. Venitatud võrestiku meetod on aga selline, kus pärast moonete vähendamist jääb alles enam-vähem regulaarne võrestik, mida saab kiiresti ja kergesti muuta vastavaks Dealunay triangulatsiooni tingimustele.