Delaunay Triangulation & Voronoi Diagrams: The Geometry of Point Sets

What Are Delaunay Triangulations?

A Delaunay triangulation for a set of points is a triangulation such that no point lies inside the circumcircle of any triangle in the triangulation. This property ensures that the triangles are as equiangular as possible, making it an optimal choice for various applications.

The Delaunay triangulation can be constructed using algorithms like Bowyer-Watson, which iteratively adds points and adjusts the existing triangulation to maintain the Delaunay condition.

Voronoi Diagrams: The Dual of Delaunay Triangulations

A Voronoi diagram partitions a plane into regions based on distance to points in a specific subset of the plane. Each region consists of all points closer to its associated point (site) than to any other site.

The Voronoi diagram is the dual graph of the Delaunay triangulation, meaning that each vertex in the Voronoi diagram corresponds to a triangle in the Delaunay triangulation and vice versa.

Why Do These Diagrams Matter?

Delaunay triangulations and Voronoi diagrams are crucial for spatial analysis, network design, and computational geometry. They help in optimizing the layout of structures, analyzing geographic data, and solving problems related to proximity and coverage.

In practical applications, these diagrams can be used to model cell phone towers, optimize road networks, and analyze biological structures like protein folding.

Real-World Applications

Delaunay triangulations are widely used in computer graphics for surface reconstruction from point clouds. They ensure that the resulting mesh is free of degenerate triangles, making it suitable for rendering and animation.

Voronoi diagrams find applications in facility location problems, where they help determine the optimal placement of facilities to minimize travel distances or costs.

Frequently asked questions

Try it live

Everything above runs in your browser — open Delaunay Triangulation & Voronoi Diagram (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.