Delaunayeva triangulacija

Delaunayeva triangulacija se imenuje po ruskem matematiku Borisu Nikolajeviču Delaunayu, ki jo je izumil leta 1934. Triangulacija je Delaunayeva, če izpolnjuje Delaunayev pogoj, ki pravi, da v nobenem krogu, ki bi bil očrtan nekemu trikotniku triangulacije, ne sme biti nobena točka. S tem se dobi triangulacijo, ki ima najmanjše število tankih trikotnikov (trikotnikov z majhnimi notranjimi koti), kar je nezaželeno in povzroča nevšečnosti v praksi.

Potek triangulacijeUredi

AlgoritmiUredi

Naključni inkrementalni algoritemUredi

Algoritmi iz te skupine so najpogosteje uporabljeni. V najslabšem primeru lahko imajo časovno zahtevnost O(N2), vendar je pričakovana časovna zahtevnost O(n log n). Obstaja več rešitev kot je na primer iskalni algoritem, ki v vsakem koraku dodaja po en pravilni trikotnik k trenutni triangulaciji in algoritem z vstavljanjem, ki zaporedoma vstavlja točke v narejeno triangulacijo, nato pa jo popravi, da zadošča Delaunayevemu pogoju.

Algoritem deli in vladajUredi

Algoritem na začetku množico vhodnih točk razdeli na manjše množice točk, nad katerimi naredi triangulacijo, nato pa te manjše množice združi in naredi celotno triangulacijo.

Algoritem s prebirno premicoUredi

Priljubljeni algoritem s prebirno premico je predlagal Steven Fortune (1987). V bistvu je Fortune razvil algoritem, ki skonstruira dualni graf Delaunayeve triangulacije - Voronojevih diagramov. Časovna zahtevnost je O(n log n).