Point set triangulation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A triangulation of a set of points P in the plane is a triangulation of the convex hull of P, with all points from P being among the vertices of the triangulation.[1] Triangulations are special cases of planar straight-line graphs.

There are special triangulations like the Delaunay triangulation which is the geometric dual of the Voronoi diagram. Subsets of the Delaunay triangulation are the Gabriel graph, nearest neighbor graph and the minimal spanning tree.

Triangulations have a number of applications, and there is an interest to find a "good" triangulation for a given point set under some criteria. One of them is a minimum-weight triangulation. Sometimes it is desirable to have a triangulation with special properties, e.g., in which all triangles have large angles (long and narrow ("splinter") triangles are avoided).

Given a set of edges that connect some pairs of the points, the problem to determine whether they contain a triangulation is NP-complete .[2]

Triangulation and convex hull[edit]

A triangulation of the set S of n-dimensional points in general position may be derived from the convex hull of a set of points S1 in the space of dimension larger by 1 which are the projections of the original point set onto the paraboloid surface x_{n+1} = x_1^2+\cdots+x_n^2. One has to construct the convex hull of the set S1 and project it back onto the space of S. If points are not in general position, additional effort is required to triangulate the non-tetrahedral facets.


The following is a table of time complexity results for different kinds of optimal point set triangulations.

minimize maximize
minimum angle O(n \log n)
(Delaunay triangulation)
maximum O(n^2 \log n) [3] [4]
minimum area O(n^2) [5] O(n^2 \log n) [6]
maximum O(n^2 \log n) [6]
maximum degree NP-complete
for degree of 7 [7]
maximum eccentricity O(n^3) [4]
minimum edge length O(n \log n)
(Closest pair of points problem)
NP-complete [8]
maximum O(n^2) [9] O(n \log n)
(using the Convex hull)
sum of NP-hard
(Minimum-weight triangulation)
minimum height O(n^2 \log n) [4]
maximum slope O(n^3) [4]

See also[edit]