# Point-set triangulation

(Redirected from Point set triangulation)
Two different triangulations of the same set of 9 points in the plane.

A triangulation of a set of points ${\displaystyle {\mathcal {P}}}$ in the Euclidean space ${\displaystyle \mathbb {R} ^{d}}$ is a simplicial complex that covers the convex hull of ${\displaystyle {\mathcal {P}}}$, and whose vertices belong to ${\displaystyle {\mathcal {P}}}$.[1] In the plane (when ${\displaystyle {\mathcal {P}}}$ is a set of points in ${\displaystyle \mathbb {R} ^{2}}$), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of ${\displaystyle {\mathcal {P}}}$ are vertices of its triangulations.[2] In this case, a triangulation of a set of points ${\displaystyle {\mathcal {P}}}$ in the plane can alternatively be defined as a maximal set of non-crossing edges between points of ${\displaystyle {\mathcal {P}}}$. In the plane, triangulations are special cases of planar straight-line graphs.

A particularly interesting kind of triangulations are the Delaunay triangulations. They are the geometric duals of Voronoi diagrams. The Delaunay triangulation of a set of points ${\displaystyle {\mathcal {P}}}$ in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of ${\displaystyle {\mathcal {P}}}$.

Triangulations have a number of applications, and there is an interest to find the "good" triangulations of a given point set under some criteria as, for instance minimum-weight triangulations. 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).[3]

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

## Regular triangulations

Some triangulations of a set of points ${\displaystyle {\mathcal {P}}\subset \mathbb {R} ^{d}}$ can be obtained by lifting the points of ${\displaystyle {\mathcal {P}}}$ into ${\displaystyle \mathbb {R} ^{d+1}}$ (which amounts to add a coordinate ${\displaystyle x_{d+1}}$ to each point of ${\displaystyle {\mathcal {P}}}$), by computing the convex hull of the lifted set of points, and by projecting the lower faces of this convex hull back on ${\displaystyle \mathbb {R} ^{d}}$. The triangulations built this way are referred to as the regular triangulations of ${\displaystyle {\mathcal {P}}}$. When the points are lifted to the paraboloid of equation ${\displaystyle x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}}$, this construction results in the Delaunay triangulation of ${\displaystyle {\mathcal {P}}}$. Note that, in order for this construction to provide a triangulation, the lower convex hull of the lifted set of points needs to be simplicial. In the case of Delaunay triangulations, this amounts to require that no ${\displaystyle d+2}$ points of ${\displaystyle {\mathcal {P}}}$ lie in the same sphere.

## Combinatorics in the plane

Every triangulation of any set ${\displaystyle {\mathcal {P}}}$ of ${\displaystyle n}$ points in the plane has ${\displaystyle 2n-h-2}$ triangles and ${\displaystyle 3n-h-3}$ edges where ${\displaystyle h}$ is the number of points of ${\displaystyle {\mathcal {P}}}$ in the boundary of the convex hull of ${\displaystyle {\mathcal {P}}}$. This follows from a straightforward Euler characteristic argument.[5]

## Algorithms to build triangulations in the plane

Triangle Splitting Algorithm : Find the convex hull of the point set ${\displaystyle {\mathcal {P}}}$ and triangulate this hull as a polygon. Choose an interior point and draw edges to the three vertices of the triangle that contains it. Continue this process until all interior points are exhausted.[6]

Incremental Algorithm : Sort the points of ${\displaystyle {\mathcal {P}}}$ according to x-coordinates. The first three points determine a triangle. Consider the next point ${\displaystyle p}$ in the ordered set and connect it with all previously considered points ${\displaystyle \{p_{1},...,p_{k}\}}$ which are visible to p. Continue this process of adding one point of ${\displaystyle {\mathcal {P}}}$ at a time until all of ${\displaystyle {\mathcal {P}}}$ has been processed.[7]

## Time complexity of various algorithms

The following table reports time complexity results for the construction of triangulations of point sets in the plane, under different optimality criteria, where ${\displaystyle n}$ is the number of points.

minimize maximize
minimum angle ${\displaystyle O(n\log n)}$
(Delaunay triangulation)
maximum ${\displaystyle O(n^{2}\log n)}$ [8] [9]
minimum area ${\displaystyle O(n^{2})}$ [10] ${\displaystyle O(n^{2}\log n)}$ [11]
maximum ${\displaystyle O(n^{2}\log n)}$ [11]
maximum degree NP-complete
for degree of 7 [12]
maximum eccentricity ${\displaystyle O(n^{3})}$ [9]
minimum edge length ${\displaystyle O(n\log n)}$
(Closest pair of points problem)
NP-complete [13]
maximum ${\displaystyle O(n^{2})}$ [14] ${\displaystyle O(n\log n)}$
(using the Convex hull)
sum of NP-hard
(Minimum-weight triangulation)
minimum height ${\displaystyle O(n^{2}\log n)}$ [9]
maximum slope ${\displaystyle O(n^{3})}$ [9]

## Notes

1. ^ De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 25. Springer.
2. ^ de Berg et al. 2008, Section 9.1.
3. ^ de Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). Springer-Verlag. ISBN 978-3-540-77973-5.
4. ^
5. ^ Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1992), "An O(n2 log n) time algorithm for the minmax angle triangulation", SIAM Journal on Scientific and Statistical Computing, 13 (4): 994–1008, CiteSeerX 10.1.1.66.2895, doi:10.1137/0913058, MR 1166172.
6. ^ Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.
7. ^ Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.
8. ^
9. ^ a b c d
10. ^
11. ^ a b
12. ^
13. ^
14. ^