Delaunay Triangulation - Properties

Properties

Let n be the number of points and d the number of dimensions.

• The union of all simplices in the triangulation is the convex hull of the points.
• The Delaunay triangulation contains O(n⌈d / 2⌉) simplices.
• In the plane (d = 2), if there are b vertices on the convex hull, then any triangulation of the points has at most 2n − 2 − b triangles, plus one exterior face (see Euler characteristic).
• In the plane, each vertex has on average six surrounding triangles.
• In the plane, the Delaunay triangulation maximizes the minimum angle. Compared to any other triangulation of the points, the smallest angle in the Delaunay triangulation is at least as large as the smallest angle in any other. However, the Delaunay triangulation does not necessarily minimize the maximum angle.
• A circle circumscribing any Delaunay triangle does not contain any other input points in its interior.
• If a circle passing through two of the input points doesn't contain any other of them in its interior, then the segment connecting the two points is an edge of a Delaunay triangulation of the given points.
• Each triangle of the Delaunay triangulation of a set of points in d-dimensional spaces corresponds to a facet of convex hull of the projection of the points onto a (d + 1)-dimensional paraboloid, and vice versa.
• The closest neighbor b to any point p is on an edge bp in the Delaunay triangulation since the nearest neighbor graph is a subgraph of the Delaunay triangulation.
• The Delaunay triangulation is a geometric spanner: the shortest path between two vertices, along Delaunay edges, is known to be no longer than times the Euclidean distance between them.