# Delaunay Triangulation and Voronoi Diagram

Using the *Delaunay triangulation* method - named after Boris Nikolajewitsch Delone - a set of points is combined to form an area-wide network of triangles.

The Problem is that there are several ways by which to triangulate any given set of points, but not all meet the requirements for the *Delaunay triangulation*. Conditions are that all three points of a triangle lie on a circle within which there are no further points and that therefore they are as “well-shaped” as possible, i.e. at best, equilateral triangles are formed.

For the following example set three triangulation variants are possible, but only the first meets the requirements for a *Delaunay triangulation*. The other variants are showing at minimum one point (green) inside the circle through the three points of one of the triangles.

The *Delaunay triangulation* is used, for example, in digital terrain models to create a TIN data structure.

The *Voronoi diagram* (also *Thiessen polygons* or *Dirichlet tessellation*) is known as the so-called dual graph of the *Delaunay triangulation*. It was named after Georgi Feodosjewitsch Woronoi and enables the subdivision of surfaces into areas of influence.

The *Voronoi diagram* is used, for example, in robotics for route planning with existing obstacles or in zoology as a model and analysis of animal territories.

## Algorithm

Given is a set of \( n \) unique points \( P \) in one level \[ P = (p_1, p_2, p_3, \cdots, p_n) \]

The *Voronoi diagram* of \( P \) is defined as subdividing the level into \( n \) cells. For each point in \( P \), a cell is created with the property that a point \( q \) is only in the cell belonging to \( p_i \) if: \[ dist(q,p_i) < dist(q,p_j) \] for every point \(p_j \in P\) with \(j \neq i\).

So, the Voronoi edges are constructed by creating the perpendicular bisector of the line between two points respectively and blending them.

The *Delaunay triangulation* of \(P\) is then created by connecting the points of all neighboring Voronoi cells.

In the end the combination of *Delaunay triangulation* and *Voronoi diagram* looks like this.

So, the Voronoi cell arises from the intersection of the perpendicular bisectors of the Delaunay triangle sides that belong together.

## Hands-On

*Delaunay triangulation*and the

*Voronoi diagram*will be calculated. You can clear the points by clicking on the

*Clear*Button or you can return to the default point set by clicking the

*Reset*Button. Change the Toggles for seeing only the

*Delaunay triangulation (orange)*or only the

*Voronoi diagram (blue)*or both.

## References

- Franz Aurenhammer, Rolf Klein, Der-Tsai Lee:
*Voronoi Diagrams and Delaunay Triangulation. World Scientific*, 2013 - Ivan Kutskir:
*Voronoi Diagram in JavaScript*, 2009, accessed July 2020 - Rolf Klein:
*Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen. Springer*, 2005 - Samuel Peterson:
*Computing Constrained Delaunay Triangulations*, 1998, accessed July 2020