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; si tende a evitare i triangoli stretti. La triangolazione prende il nome da Boris Delaunay per il suo lavoro su questo argomento dal 1934.

Una triangolazione di Delaunay; sono mostrati i circumcerchi.

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.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla Triangolazione di Delaunay

Collegamenti esterni

• (EN) Eric W. Weisstein, Delaunay Triangulation, su MathWorld, Wolfram Research.
• (EN) Delaunay triangulation, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Delaunay triangulation, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL