top of page
Search
Writer's pictureElias Gabriel

What are Delaunay Triangulations?

Updated: Dec 17, 2020

Delaunay triangulations are closely connected to Voronoi diagrams. Named after the Soviet-era mathematician Boris Delaunay, the Delaunay triangulation of a set of points is the set of triangles that connect all the points together to form a web, with each triangle having the largest possible internal angles. In any triangulation, the smallest angle is always maximized (Wolfram, Wikipedia).


These triangulations are incredibly useful for just about as many things as Voronoi diagrams, from CAD and 3D modeling to video game development. They provide simple ways to create a discrete surface over any set of points, and ensure that the triangles produced are the largest possible with few if any thin angles.



A Delaunay triangulation of a random graph, with circumcircles show for each triangle.

Image credit: Wikipedia


A Delaunay triangulation is a triangulation of all the points in P such that all the circumcircles of each triangle are empty.
Diagram of invalid and valid Delaunay tringulations of a quadrilateral.

Image credit: DataGenetics


Sliver triangles compared to "regular" triangles.

Image credit: DataGenetics


Delaunay triangulations are only unique for circles that touch only three points.

The avoidance of sliver triangles proves extremely helpful for computer graphics and 3D modeling, as larger-angled triangles behave better in physics simulations and surface texturing than thinner ones.

 

Resources

  1. Weisstein, Eric W. "Delaunay Triangulation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DelaunayTriangulation.html

  2. “Delaunay Triangulation.” Wikipedia, Wikimedia Foundation, 13 Dec. 2020, https://en.wikipedia.org/wiki/Delaunay_triangulation

  3. "Voronoi Tessellations." DataGenetics, 01 May 2017, https://datagenetics.com/blog/may12017/index.html

24 views

Recent Posts

See All

コメント


bottom of page