Delaunay Triangulation In Two and Three Dimensions

What is a Delaunay triangulation ?

• A triangulation is a subdivision of an area (volume) into triangles (tetrahedrons).
• The Delaunay triangulation has the property that the circumcircle (circumsphere) of every triangle (tetrahedron) does not contain any points of the triangulation.
• The Delaunay triangulation is the dual structure of the Voronoi diagram.

---

Voronoi diagram

The Voronoi diagram of a point set P is a subdivision of the plane with the property that each Voronoi cell of vertex p contains all locations that are closer to p than to every other vertex of P. The vertices P are also called Voronoi generators. Each edge of a Voronoi cell is the bisector of the connection of p to the corresponding neighbour cell. Each intersection of Voronoi edges belongs to at least three Voronoi cells and is the center of the circle through the generators of these three cells. These three vertices form a Delaunay triangle.

Delaunay triangulation and Voronoi diagram of a pointset of hundred vertices.

Voronoi diagram of 1000 vertices

Applications

• Simulation of the growth of cristals
• Metallurgy (examination of alloys)
• Cartography, town planning
• Computation of neighbouring problems (computational geometry)
• Mesh generation for finite elements methods, stereolithography, visualization of surfaces, etc.

---

Implemented algorithms

• The flipping algorithm (only 2D) starts with an arbitrary triangulation and converts it into the Delaunay triangulation by flipping the diagonals of two neighbouring triangles. Two neighbouring triangles t1=(p0,p1,p2) and t2=(p3,p2,p1) are flipped to t1'=(p0,p1,p3) and t2'=(p2,p0,p3), if vertex p3 lies in the circumcircle of t1 (respectively p0 lies in the circumcircle of t2).

  Literature:

  R.Sibson. Locally equiangular triangulations. The Computer Journal Vol.2 (3): 243-245, 1973.

  MPEG (600 kB)

• The randomized incremental insertion algorithm starts with a start simplex (triangle or tetrahedron) and inserts the points in random order into the triangulation.

  Literature:

  L.J.Guibas, D.E.Knuth and M.Sharir. Randomized Incremental Construction of Delaunay and Voronoi diagrams. Algorithmica 7: 381-413, 1992.

  Methods for finding the enclosing simplex of a point:

  1. Quadtree, Octree
  2. Delaunay tree

  MPEG (421 kB)

• The incremental construction algorithm adds new Delaunay triangles (tetrahedrons) to an existing triangulation. Searching methods for the computation of Delaunay simplices are the regular grid and the sparse matrix.

  Literature:

  1. T.Fang and L.Piegl. Delaunay triangulation using a uniform grid. IEEE Computer Graphics and Applications: 36-47, 1993.
  2. T.Fang and L.Piegl. Algorithm for Delaunay triangulation and convex hull computation using a sparse matrix. Computer Aided Design Vol.24(8): 425-436, 1992.

  MPEG (333 kB)

• The Delaunay wall algorithm is a "first-merge divide-and-conquor" algorithm. Before the subdivision all simplices on the frontier (wall) of both partial areas are computed. The triangulations of the partial areas are computed recursively.

  Literature:

  P.Cignoni, C.Montani, R.Perego and R.Scopigno. Parallel 3D Delaunay Triangulation. Eurographics 93: 129-142, 1993.

  MPEG (396 kB)

• The planesweep algorithm (only 2D) computes Delaunay edges and Delaunay triangles by moving a sweepline over the area.

  Literature:

  S.Fortune. Sweepline Algorithms for Voronoi diagrams. Algorithmica 2: 153-174, 1987.

  MPEG (512 kB)

---

Further algorithms

• The divide-and-conquer algorithm subdivides the area into two partial areas, computes recursively the Delaunay triangulation of the partial areas and merges finally both triangulations.

  Literature:

  R.Dwyer. A faster divide and conquer algorithm for constructing Delaunay triangulations. Algorithmica 2: 137-151, 1989.

• The higher dimension embedding algorithm transforms the points in E^(d+1) ( f(x,y)=(x,y,x^2+y^2) ) and then computes the convex hull of the transformed points. The Delaunay triangulation is obtained by simply projecting the convex hull in the original dimension.

---

Comparison of the two dimensional algorithms

Performance of the algorithms for Delaunay triangulation computation of regularly distributed point set, measured on a SGI R4000.

• Insert = randomized insertion algorithm
• DeWall = Delaunay wall algorithm without searching structure
• Matrix = with sparse matrix
• Grid = with regular grid
• Flipping = flipping algorithm plus computation of the start triangulation
• PlaneSweep = planesweep algorithm
• Quadtree = randomized insertion algorithm using a quadtree for locating the enclosing triangle

---

Comparison of the three dimensional algorithms

Performance of the algorithms for Delaunay triangulation computation of regularly distributed point set, measured on a SGI R4000.

• Octree= randomized insertion algorithm using an octree for locating the enclosing tetrahedron
• DeWall = Delaunay wall algorithm without searching structure
• Matrix = with sparse matrix
• Gitter = with regular grid
• Insert = randomized insertion algorithm

---

---

Master thesis by Jörg Krämer, Dec.1995

Jörg Krämer: kraemerj@gris.uni-tuebingen.de