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 triangulacije

• 
  Slika 1. Naključne točke
• 
  Slika 2. Triangulacija
• 
  Slika. 3. Pregled ali izpolnjuje Delaunayev pogoj

Algoritmi

Naključni inkrementalni algoritem

Algoritmi iz te skupine so najpogosteje uporabljeni. V najslabšem primeru lahko imajo časovno zahtevnost O(N²), 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 vladaj

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 premico

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).

• 
  Poišče se središča očrtanih krogov
• 
  Dobljene točke se poveže in tako nastane Voronojev diagram