Triangolazione di Delaunay

In geometria computazionale, la triangolazione di Delaunay per un gruppo di punti P su un piano è una triangolazione DT(P) tale che nessun punto appartenente a P sia all'interno del circumcerchio di ogni triangolo in DT(P). La triangolazione di Delaunay massimizza il minor angolo di tutti gli angoli dei triangoli nella triangolazione^{[poco chiaro, formalizzare]}; si tende a evitare i triangoli stretti. La triangolazione prende il nome da Boris Delaunay per il suo lavoro su questo argomento dal 1934.

Per un gruppo di punti su una stessa linea non esiste triangolazione (in quanto non si possono formare triangoli non degeneri). Per un gruppo di quattro o più punti su una stessa circonferenza (ad esempio i vertici di un rettangolo) la triangolazione non è unica: ognuno dei due possibili triangoli in cui si può dividere il quadrilatero, infatti, soddisfa i requisiti di Delaunay (ovvero che le circonferenze circoscritte ai triangoli non contengano altri punti).

Considerando le sfere circoscritte, le nozioni della triangolazione di Delaunay si possono estendere a tre o più dimensioni. Generalizzazioni possono essere applicate a metriche diverse da quella euclidea. In quest'ultimo caso non è garantito che la triangolazione esista o sia unica.