Point-set triangulation

Last updated October 30, 2024

A triangulation of a set of points ${\mathcal {P}}$ in the Euclidean space $\mathbb {R} ^{d}$ is a simplicial complex that covers the convex hull of ${\mathcal {P}}$ , and whose vertices belong to ${\mathcal {P}}$ .^[1] In the plane (when ${\mathcal {P}}$ is a set of points in $\mathbb {R} ^{2}$ ), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of ${\mathcal {P}}$ are vertices of its triangulations.^[2] In this case, a triangulation of a set of points ${\mathcal {P}}$ in the plane can alternatively be defined as a maximal set of non-crossing edges between points of ${\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 ${\mathcal {P}}$ in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of ${\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 ${\mathcal {P}}\subset \mathbb {R} ^{d}$ can be obtained by lifting the points of ${\mathcal {P}}$ into $\mathbb {R} ^{d+1}$ (which amounts to add a coordinate $x_{d+1}$ to each point of ${\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 $\mathbb {R} ^{d}$ . The triangulations built this way are referred to as the regular triangulations of ${\mathcal {P}}$ . When the points are lifted to the paraboloid of equation $x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}$ , this construction results in the Delaunay triangulation of ${\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 $d+2$ points of ${\mathcal {P}}$ lie in the same sphere.

Combinatorics in the plane

Every triangulation of any set ${\mathcal {P}}$ of $n$ points in the plane has $2n-h-2$ triangles and $3n-h-3$ edges where $h$ is the number of points of ${\mathcal {P}}$ in the boundary of the convex hull of ${\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 ${\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 ${\mathcal {P}}$ according to x-coordinates. The first three points determine a triangle. Consider the next point $p$ in the ordered set and connect it with all previously considered points $\{p_{1},...,p_{k}\}$ which are visible to p. Continue this process of adding one point of ${\mathcal {P}}$ at a time until all of ${\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 $n$ is the number of points.

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

Notes

↑ 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.
↑ de Berg et al. 2008, Section 9.1.
↑ 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.
↑ Lloyd 1977.
↑ Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1992), "An O(n² 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 .
↑ Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.
↑ Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.
↑ Edelsbrunner, Tan & Waupotitsch 1990.
1 2 3 4 Bern et al. 1993.
↑ Chazelle, Guibas & Lee 1985.
1 2 Vassilev 2005.
↑ Jansen 1992.
↑ Fekete 2012.
↑ Edelsbrunner & Tan 1991.

Related Research Articles

In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points. This maximizes the size of the smallest angle in any of the triangles, and tends to avoid sliver triangles.

In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane. For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.

<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

In computational geometry, polygon triangulation is the partition of a polygonal area $P$ into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$ .

<span class="mw-page-title-main">Arrangement of lines</span> Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given $n$ points and $m$ lines in the Euclidean plane, the number of incidences is

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

<span class="mw-page-title-main">Orthogonal convex hull</span> Minimal superset that intersects each axis-parallel line in an interval

In geometry, a set $K \subset R d$ is defined to be orthogonally convex if, for every line $L$ that is parallel to one of standard basis vectors, the intersection of $K$ with $L$ is empty, a point, or a single segment. The term "orthogonal" refers to corresponding Cartesian basis and coordinates in Euclidean space, where different basis vectors are perpendicular, as well as corresponding lines. Unlike ordinary convex sets, an orthogonally convex set is not necessarily connected.

<span class="mw-page-title-main">K-set (geometry)</span> Points separated from others by a line

In discrete geometry, a $-set of a finite point set in the Euclidean plane is a subset of elements of that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a -set of a finite point set is a subset of elements that can be separated from the remaining points by a hyperplane. In particular, when, the line or hyperplane that separates a -set from the rest of is a halving line or halving plane .$

<span class="mw-page-title-main">Pseudotriangle</span>

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points $and by an edge whenever there does not exist a third point that is closer to both and than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set.$

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form

In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges, unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.

In computational geometry, an alpha shape, or α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points. They were first defined by Edelsbrunner, Kirkpatrick & Seidel (1983). The alpha-shape associated with a set of points is a generalization of the concept of the convex hull, i.e. every convex hull is an alpha-shape but not every alpha shape is a convex hull.

In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

<span class="mw-page-title-main">Flip graph</span> A graph that encodes local operations in mathematics

In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are special cases of geometric graphs.

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

References

Bern, M.; Edelsbrunner, H.; Eppstein, D.; Mitchell, S.; Tan, T. S. (1993), "Edge insertion for optimal triangulations", Discrete and Computational Geometry , 10 (1): 47–65, doi: 10.1007/BF02573962 , MR 1215322
Chazelle, Bernard; Guibas, Leo J.; Lee, D. T. (1985). "The power of geometric duality" (PDF). BIT. 25 (1). BIT Computer Science and Numerical Mathematics: 76–90. doi:10.1007/BF01934990. ISSN 0006-3835. S2CID 122411548.
de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry: Algorithms and Applications (3 ed.). Springer-Verlag.
O'Rourke, Joseph; L. Devadoss, Satyan (2011). Discrete and Computational Geometry (1 ed.). Princeton University Press.
Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1990). An O(n2log n) time algorithm for the MinMax angle triangulation. Proceedings of the sixth annual symposium on Computational geometry. SCG '90. ACM. pp. 44–52. CiteSeerX 10.1.1.66.2895 . doi:10.1145/98524.98535. ISBN 0-89791-362-0.
Edelsbrunner, Herbert; Tan, Tiow Seng (1991). A quadratic time algorithm for the minmax length triangulation. 32nd Annual Symposium on Foundations of Computer Science. pp. 414–423. CiteSeerX 10.1.1.66.8959 . doi:10.1109/SFCS.1991.185400. ISBN 0-8186-2445-0.
Fekete, Sándor P. (2012). "The Complexity of MaxMin Length Triangulation". arXiv: 1208.0202v1 [cs.CG].
Jansen, Klaus (1992). The Complexity of the Min-max Degree Triangulation Problem (PDF). 9th European Workshop on Computational Geometry. pp. 40–43.
Lloyd, Errol Lynn (1977). On triangulations of a set of points in the plane. 18th Annual Symposium on Foundations of Computer Science (SFCS 1977). pp. 228–240. doi:10.1109/SFCS.1977.21.
Vassilev, Tzvetalin Simeonov (2005). Optimal Area Triangulation (PDF) (Ph.D.). University of Saskatchewan, Saskatoon. Archived from the original (PDF) on 2017-08-13. Retrieved 2013-06-15.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[DRS-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.

[FOOTNOTEde_Bergvan_KreveldOvermarsSchwarzkopf2008Section_9.1-2] Berg et al. 2008, Section 9.1.

[deBerg-3] Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). Springer-Verlag. ISBN 978-3-540-77973-5.

[FOOTNOTELloyd1977-4] Lloyd 1977.

[5] Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1992), "An O(n² 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.

[FOOTNOTEEdelsbrunnerTanWaupotitsch1990-8] Edelsbrunner, Tan & Waupotitsch 1990.

[FOOTNOTEBernEdelsbrunnerEppsteinMitchell1993-9] 1 2 3 4 Bern et al. 1993.

[FOOTNOTEChazelleGuibasLee1985-10] Chazelle, Guibas & Lee 1985.

[FOOTNOTEVassilev2005-11] 1 2 Vassilev 2005.

[FOOTNOTEJansen1992-12] Jansen 1992.

[FOOTNOTEFekete2012-13] Fekete 2012.

[FOOTNOTEEdelsbrunnerTan1991-14] Edelsbrunner & Tan 1991.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]