Minimum-weight triangulation

Last updated January 16, 2024

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length.^[1] 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.

History

The problem of minimum weight triangulation of a point set was posed by Düppe & Gottschalk (1970), who suggested its application to the construction of triangulated irregular network models of land countours, and used a greedy heuristic to approximate it. Shamos & Hoey (1975) conjectured that the minimum weight triangulation always coincided with the Delaunay triangulation, but this was quickly disproved by Lloyd (1977), and indeed Kirkpatrick (1980) showed that the weights of the two triangulations can differ by a linear factor.^[2]

The minimum-weight triangulation problem became notorious when Garey & Johnson (1979) included it in a list of open problems in their book on NP-completeness, and many subsequent authors published partial results on it. Finally, Mulzer & Rote (2008) showed it to be NP-hard, and Remy & Steger (2009) showed that accurate approximations to it can be constructed efficiently.

Complexity

The weight of a triangulation of a set of points in the Euclidean plane is defined as the sum of lengths of its edges. Its decision variant is the problem of deciding whether there exists a triangulation of weight less than a given weight; it was proven to be NP-hard by Mulzer & Rote (2008). Their proof is by reduction from PLANAR-1-IN-3-SAT, a special case of the Boolean satisfiability problem in which a 3-CNF whose graph is planar is accepted when it has a truth assignment that satisfies exactly one literal in each clause. The proof uses complex gadgets, and involves computer assistance to verify the correct behavior of these gadgets.

It is not known whether the minimum-weight triangulation decision problem is NP-complete, since this depends on the known open problem whether the sum of radicals may be computed in polynomial time. However, Mulzer and Rote remark that the problem is NP-complete if the edge weights are rounded to integer values.

Although NP-hard, the minimum weight triangulation may be constructed in subexponential time by a dynamic programming algorithm that considers all possible simple cycle separators of $O({\sqrt {n}})$ points within the triangulation, recursively finds the optimal triangulation on each side of the cycle, and chooses the cycle separator leading to the smallest total weight. The total time for this method is $2^{O({\sqrt {n}}\log n)}$ .^[3]

Approximation

Several authors have proven results relating the minimum weight triangulation to other triangulations in terms of the approximation ratio, the worst-case ratio of the total edge length of the alternative triangulation to the total length of the minimum weight triangulation. In this vein, it is known that the Delaunay triangulation has an approximation ratio of $\Theta (n)$ ,^[4] and that the greedy triangulation (the triangulation formed by adding edges in order from shortest to longest, at each step including an edge whenever it does not cross an earlier edge) has an approximation ratio of $\Theta ({\sqrt {n}})$ .^[5] Nevertheless, for randomly distributed point sets, both the Delaunay and greedy triangulations are within a logarithmic factor of the minimum weight.^[6]

The hardness result of Mulzer and Rote also implies the NP-hardness of finding an approximate solution with relative approximation error at most O(1/n²). Thus, a fully polynomial approximation scheme for minimum weight triangulation is unlikely. However, a quasi-polynomial approximation scheme is possible: for any constant ε 0, a solution with approximation ratio 1 + ε can be found in quasi-polynomial time exp(O((log n)⁹).^[7]

Heuristics

Because of the difficulty of finding the exact solutions of the minimum-weight triangulation, many authors have studied heuristics that may in some cases find the solution although they cannot be proven to work in all cases. In particular, much of this research has focused on the problem of finding sets of edges that are guaranteed to belong to the minimum-weight triangulation. If a subgraph of the minimum-weight triangulation found in this way turns out to be connected, then the remaining untriangulated space may be viewed as forming a simple polygon, and the entire triangulation may be found by using dynamic programming to find the optimal triangulation of this polygonal space. The same dynamic programming approach can also be extended to the case that the subgraph has a bounded number of connected components^[8] and the same approach of finding a connected graph and then applying dynamic programming to fill in the polygonal gaps surrounding the graph edges has also been used as part of heuristics for finding low-weight but not minimum-weight triangulations.^[9]

The graph formed by connecting two points whenever they are each other's nearest neighbors is necessarily a subgraph of the minimum-weight triangulation.^[10] However, this mutual nearest neighbor graph is a matching, and hence is never connected. A related line of research finds large subgraphs of the minimum-weight triangulation by using circle-based β-skeletons, the geometric graphs formed by including an edge between two points u and v whenever there does not exist a third point w forming an angle uwv greater than some parameter θ. It has been shown that, for sufficiently small values of θ, the graph formed in this way is a subgraph of the minimum-weight triangulation.^[11] However, the choice of θ needed to ensure this is smaller than the angle {{{1}}} for which the β-skeleton is always connected.

A more sophisticated technique called the LMT-skeleton was proposed by Dickerson & Montague (1996). It is formed by an iterative process, in which two sets of edges are maintained, a set of edges known to belong to the minimum-weight triangulation and a set of edges that are candidates to belong to it. Initially, the set of known edges is initialized to the convex hull of the input, and all remaining pairs of vertices form candidate edges. Then, in each iteration of the construction process, candidate edges are removed whenever there is no pair of triangles formed by the remaining edges forming a quadrilateral for which the candidate edge is the shortest diagonal, and candidate edges are moved to the set of known edges when there is no other candidate edge that crosses them. The LMT-skeleton is defined to be the set of known edges produced after this process stops making any more changes. It is guaranteed to be a subgraph of the minimum-weight triangulation, can be constructed efficiently, and in experiments on sets of up to 200 points it was frequently connected.^[12] However it has been shown that on the average for large point sets it has a linear number of connected components.^[13]

Other heuristics that have been applied to the minimum weight triangulation problem include genetic algorithms ^[14] branch and bound,^[15] and ant colony optimization algorithms.^[16]

Variations

A polygon triangulation of minimal weight may be constructed in cubic time using the dynamic programming approach, reported independently by Gilbert (1979) and Klincsek (1980). In this method, the vertices are numbered consecutively around the boundary of the polygon, and for each diagonal from vertex i to vertex j that lies within the polygon, the optimal triangulation is calculated by considering all possible triangles ijk within the polygon, adding the weights of the optimal triangulations below the diagonals ik and jk, and choosing the vertex k that leads to the minimum total weight. That is, if MWT(i,j) denotes the weight of the minimum-weight triangulation of the polygon below edge ij, then the overall algorithm performs the following steps:

For each possible value of i, from n − 1 down to 1, do:
- For each possible value of j, from i + 1 to n, do:
  - If ij is an edge of the polygon, set MWT(i,j) = length(ij)
  - Else if ij is not an interior diagonal of the polygon, set MWT(i,j) = +∞
  - Else set MWT(i,j) = length(ij) + min_{i < k < j} MWT(i,k) + MWT(k,j)

After this iteration completes, MWT(1,n) will store the total weight of the minimum weight triangulation. The triangulation itself may be obtained by recursively searching through this array, starting from MWT(1,n), at each step choosing the triangle ijk that leads to the minimum value for MWT(i,j) and recursively searching MWT(i,k) and MWT(j,k).

Similar dynamic programming methods may also be adapted to point set inputs where all but a constant number of points lie on the convex hull of the input,^[17] and to point sets that lie on a constant number of nested convex polygons or on a constant number of lines no two of which cross within the convex hull.^[18]

It is also possible to formulate a version of the point set or polygon triangulation problems in which one is allowed to add Steiner points, extra vertices, in order to reduce the total edge length of the resulting triangulations. In some cases, the resulting triangulation may be shorter than the minimum weight triangulation by as much as a linear factor. It is possible to approximate the minimum weight Steiner triangulation of a point set to within a constant factor of optimal, but the constant factor in the approximation is large.^[19]

Related problems that have also been studied include the construction of minimum-weight pseudotriangulations ^[20] and the characterization of the graphs of minimum-weight triangulations.^[21]

Notes

↑ For surveys of the problem, see Xu (1998), Levcopoulos (2008), and De Loera, Rambau & Santos (2010).
↑ See also Manacher & Zobrist (1979).
↑ Lingas (1998).
↑ Kirkpatrick (1980). A weaker bound was given by Manacher & Zobrist (1979).
↑ A family of examples proving that the approximation ratio is $\Omega ({\sqrt {n}})$ was given by Levcopoulos (1987), and the matching upper bound is by Levcopoulos & Krznaric (1998). As with the approximation ratio for Delaunay triangulation, a weaker bound was also given by Manacher & Zobrist (1979).
↑ Lingas (1986).
↑ Remy & Steger (2009). For earlier results on polynomial-time approximation algorithms, see Plaisted & Hong (1987) (log-factor approximation) and Levcopoulos & Krznaric (1998) (constant-factor approximation).
↑ Cheng, Golin & Tsang (1995).
↑ Lingas (1987); Heath & Pemmaraju (1994).
↑ Yang, Xu & You (1994).
↑ Keil (1994); Cheng, Golin & Tsang (1995); Cheng & Xu (2001); Hu (2010).
↑ Dickerson & Montague (1996); Cheng, Katoh & Sugai (1996); Beirouti & Snoeyink (1998); Aichholzer, Aurenhammer & Hainz (1999).
↑ Bose, Devroye & Evans (1996).
↑ Qin, Wang & Gong (1997); Capp & Julstrom (1998).
↑ Kyoda et al. (1997).
↑ Jahani, Bigham & Askari (2010).
↑ Hoffmann & Okamoto (2004); Grantson, Borgelt & Levcopoulos (2005); Knauer & Spillner (2006).
↑ Anagnostou & Corneil (1993); Meijer & Rappaport (1992).
↑ Eppstein (1994).
↑ Gudmundsson & Levcopoulos (2007); Aichholzer et al. (2009).
↑ Lenhart & Liotta (2002).

Related Research Articles

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set $of vertices such that for every two vertices in, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.$

<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$ .

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 art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

<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 π.

A geometric spanner or a $t$ -spanner graph or a $t$ -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a $t$ -path between any pair of vertices for a fixed parameter $t$ . A $t$ -path is defined as a path through the graph with weight at most $t$ times the spatial distance between its endpoints. The parameter $t$ is called the stretch factor or dilation factor of the spanner.

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 graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum $k$ for which a clique cover exists is called the clique cover number of the given graph.

In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant $such that the worst-case running time of the algorithm, on inputs of size, has an upper bound of the form$

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

In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane. Two points p and q are connected by an edge whenever all the angles prq are sharper than a threshold determined from the numerical parameter β.

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.

In geometry, a partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

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.

Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects. They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.

References

Aichholzer, Oswin; Aurenhammer, Franz; Hackl, Thomas; Speckmann, Bettina (2009), "On minimum weight pseudo-triangulations", Computational Geometry Theory and Applications , 42 (6–7): 627–631, doi: 10.1016/j.comgeo.2008.10.002 , MR 2519380 .
Aichholzer, Oswin; Aurenhammer, Franz; Hainz, Reinhard (1999), "New results on MWT subgraphs", Information Processing Letters, 69 (5): 215–219, doi:10.1016/S0020-0190(99)00018-6 .
Anagnostou, Efthymios; Corneil, Derek (1993), "Polynomial-time instances of the minimum weight triangulation problem", Computational Geometry. Theory and Applications , 3 (5): 247–259, doi: 10.1016/0925-7721(93)90016-Y , MR 1251594 .
Beirouti, Ronald; Snoeyink, Jack (1998), "Implementations of the LMT heuristic for minimum weight triangulation", Proc. 14th ACM Symposium on Computational Geometry, pp. 96–105, doi: 10.1145/276884.276895 , S2CID 15102126 .
Bose, Prosenjit; Devroye, Luc; Evans, William (1996), "Diamonds are not a minimum weight triangulation's best friend", Proc. 8th Canadian Conference on Computational Geometry (CCCG 1996) (PDF), pp. 68–73.
Capp, Kerry; Julstrom, Bryant A. (1998), "A weight-coded genetic algorithm for the minimum weight triangulation problem", Proc. ACM Symposium on Applied Computing, Atlanta, Georgia, United States, pp. 327–331, doi:10.1145/330560.330833, S2CID 13589205, Semantic Scholar {{citation}}: CS1 maint: location missing publisher (link).
Cheng, Siu-Wing; Golin, Mordecai; Tsang, J. (1995), "Expected case analysis of β-skeletons with applications to the construction of minimum weight triangulations", Proc. 7th Canadian Conference on Computational Geometry (CCCG 1995), pp. 279–284.
Cheng, Siu-Wing; Katoh, Naoki; Sugai, Manabu (1996), "A study of the LMT-skeleton", Algorithms and Computation, Lecture Notes in Computer Science, vol. 1178, pp. 256–265, doi:10.1007/BFb0009502, ISBN 978-3-540-62048-8 .
Cheng, Siu-Wing; Xu, Yin-Feng (2001), "On β-skeleton as a subgraph of the minimum weight triangulation", Theoretical Computer Science, 262 (1–2): 459–471, doi: 10.1016/S0304-3975(00)00318-2 .
De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), "3.2.3 Greedy and minimum weight triangulations", Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 25, Springer, pp. 102–107, ISBN 978-3-642-12970-4 .
Dickerson, Matthew T.; Montague, Mark H. (1996), "A (usually?) connected subgraph of the minimum weight triangulation", Proc. 12th ACM Symposium on Computational Geometry, pp. 204–213, doi:10.1145/237218.237364, S2CID 18962760 .
Düppe, R. D.; Gottschalk, H. J. (1970), "Automatische Interpolation von Isolinien bei willkürlich verteilten Stützpunkten", Allgemeine Vermessungs-Nachrichten, 77: 423–426. As cited by Mulzer & Rote (2008) and Remy & Steger (2009).
Eppstein, David (1994), "Approximating the minimum weight Steiner triangulation" (PDF), Discrete and Computational Geometry , 11 (2): 163–191, doi: 10.1007/BF02574002 , MR 1254088 .
Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco, Calif.: W. H. Freeman, Problem OPEN12, p. 288, ISBN 0-7167-1045-5, MR 0519066 .
Gilbert, P. D. (1979), New results in planar triangulations, Report R-850, Urbana, Illinois: Coordinated Science Laboratory, University of Illinois.
Grantson, M.; Borgelt, C.; Levcopoulos, C. (2005), "Minimum weight triangulation by cutting out triangles", Proc. 16th International Symposium on Algorithms and Computation, pp. 984–994.
Gudmundsson, Joachim; Levcopoulos, Christos (2007), "Minimum weight pseudo-triangulations", Computational Geometry Theory and Applications , 38 (3): 139–153, doi: 10.1016/j.comgeo.2007.05.004 , MR 2352529 .
Heath, L. S.; Pemmaraju, S. V. (1994), "New results for the minimum weight triangulation problem", Algorithmica , 12 (6): 533–552, doi:10.1007/BF01188718, hdl: 10919/19701 , MR 1297812, S2CID 21160664 .
Hoffmann, M.; Okamoto, Y. (2004), "The minimum weight triangulation problem with few inner points", Proc. 1st International Workshop on Parameterized and Exact Computation, pp. 200–212.
Hu, Shiyan (2010), "A new asymmetric inclusion region for minimum weight triangulation", Journal of Global Optimization, 46 (1): 63–73, CiteSeerX 10.1.1.377.6164 , doi:10.1007/s10898-009-9409-z, MR 2566136, S2CID 869128 .
Jahani, M.; Bigham, B.S.; Askari, A. (2010), "An ant colony algorithm for the minimum weight triangulation", International Conference on Computational Science and Its Applications (ICCSA), pp. 81–85, doi:10.1109/ICCSA.2010.38, S2CID 11790811, Semantic Scholar .
Keil, J. Mark (1994), "Computing a subgraph of the minimum weight triangulation", Computational Geometry: Theory & Applications , 4 (1): 18–26, doi: 10.1016/0925-7721(94)90014-0 .
Kirkpatrick, David G. (1980), "A note on Delaunay and optimal triangulations", Information Processing Letters, 10 (3): 127–128, doi:10.1016/0020-0190(80)90062-9, MR 0566856 .
Klincsek, G. T. (1980), "Minimal triangulations of polygonal domains", Annals of Discrete Mathematics, 9: 121–123, doi:10.1016/s0167-5060(08)70044-x, ISBN 9780444861115 .
Knauer, Christian; Spillner, Andreas (2006), "A fixed-parameter algorithm for the minimum weight triangulation problem based on small graph separators", Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 4271, Berlin: Springer, pp. 49–57, doi:10.1007/11917496_5, ISBN 978-3-540-48381-6, MR 2290717 .
Kyoda, Yoshiaki; Imai, Keiko; Takeuchi, Fumihiko; Tajima, Akira (1997), "A branch-and-cut approach for minimum weight triangulation", Algorithms and Computation (Singapore, 1997), Lecture Notes in Computer Science, vol. 1350, Berlin: Springer, pp. 384–393, doi:10.1007/3-540-63890-3_41, ISBN 978-3-540-63890-2, MR 1651067 .
Lenhart, William; Liotta, Giuseppe (2002), "The drawability problem for minimum weight triangulations", Theoretical Computer Science, 270 (1–2): 261–286, doi:10.1016/S0304-3975(00)00383-2, MR 1871072 .
Levcopoulos, Christos (1987), "An Ω(√n) lower bound for the nonoptimality of the greedy triangulation", Information Processing Letters, 25 (4): 247–251, doi:10.1016/0020-0190(87)90170-0, MR 0896144 .
Levcopoulos, Christos (2008), "Minimum Weight Triangulation", in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms, Springer, pp. 546–548, ISBN 978-0-387-30770-1 .
Levcopoulos, C.; Krznaric, D. (1998), "Quasi-greedy triangulations approximating the minimum weight triangulation" (PDF), Journal of Algorithms, 27 (2): 303–338, doi:10.1006/jagm.1997.0918, MR 1622398, S2CID 13991653 .
Lingas, Andrzej (1986), "The Greedy and Delaunay triangulations are not bad in the average case", Information Processing Letters, 22 (1): 25–31, doi:10.1016/0020-0190(86)90038-4 .
Lingas, Andrzej (1987), "A new heuristic for minimum weight triangulation", SIAM Journal on Algebraic and Discrete Methods, 8 (4): 646–658, doi:10.1137/0608053, MR 0918066 .
Lingas, Andrzej (1998), "Subexponential-time algorithms for minimum weight triangulations and related problems", Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98) .
Lloyd, E. (1977), "On triangulations of a set of points in the plane", Proc. 18th IEEE Symposium on Foundations of Computer Science, pp. 228–240.
Manacher, Glenn K.; Zobrist, Albert L. (1979), "Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation", Information Processing Letters, 9 (1): 31–34, doi:10.1016/0020-0190(79)90104-2, MR 0537055 .
Meijer, Henk; Rappaport, David (1992), "Computing the minimum weight triangulation of a set of linearly ordered points", Information Processing Letters, 42 (1): 35–38, doi:10.1016/0020-0190(92)90129-J, MR 1160443 .
Mulzer, Wolfgang; Rote, Günter (2008), "Minimum-weight triangulation is NP-hard", Journal of the ACM , 55 (2), Article A11, arXiv: cs.CG/0601002 , doi:10.1145/1346330.1346336, S2CID 1658062 .
Plaisted, D. A.; Hong, J. (1987), "A heuristic triangulation algorithm", Journal of Algorithms, 8 (3): 405–437, doi:10.1016/0196-6774(87)90020-4 .
Qin, Kaihuai; Wang, Wenping; Gong, Minglun (1997), "A genetic algorithm for the minimum weight triangulation", IEEE International Conference on Evolutionary Computation, pp. 541–546, doi:10.1109/ICEC.1997.592370, hdl: 10722/45578 , S2CID 18775737, Semantic Scholar .
Remy, Jan; Steger, Angelika (2009), "A quasi-polynomial time approximation scheme for minimum weight triangulation", Journal of the ACM , 56 (3), Article A15, doi:10.1145/1516512.1516517, S2CID 1781658 .
Shamos, M. I.; Hoey, D. J. (1975), "Closest-point problems", Proc. 16th IEEE Symposium on Foundations of Computer Science (PDF), pp. 151–162.
Wang, Cao An; Yang, Boting (2001), "A lower bound for β-skeleton belonging to minimum weight triangulations", Computational Geometry: Theory & Applications , 19 (1): 35–46, doi:10.1016/S0925-7721(01)00008-6 .
Xu, Yin-Feng (1998), "Minimum weight triangulations", Handbook of Combinatorial Optimization, Vol. 2, Boston, MA: Kluwer Academic Publishers, pp. 617–634, MR 1665412 .
Yang, Bo Ting; Xu, Yin Feng; You, Zhao Yong (1994), "A chain decomposition algorithm for the proof of a property on minimum weight triangulations", in Du, Ding-Zhu; Zhang, Xiang-Sun (eds.), Algorithms and Computation: 5th International Symposium, ISAAC '94, Beijing, P. R. China, August 25–27, 1994, Proceedings, Lecture Notes in Computer Science, vol. 834, Berlin: Springer, pp. 423–427, doi:10.1007/3-540-58325-4_207, ISBN 978-3-540-58325-7, MR 1316441 .

External links

Minimum Weight Triangulation using an LMT Skeleton source code'

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.

[1] For surveys of the problem, see Xu (1998), Levcopoulos (2008), and De Loera, Rambau & Santos (2010).

[2] See also Manacher & Zobrist (1979).

[3] Lingas (1998).

[4] Kirkpatrick (1980). A weaker bound was given by Manacher & Zobrist (1979).

[5] A family of examples proving that the approximation ratio is $\Omega ({\sqrt {n}})$ was given by Levcopoulos (1987), and the matching upper bound is by Levcopoulos & Krznaric (1998). As with the approximation ratio for Delaunay triangulation, a weaker bound was also given by Manacher & Zobrist (1979).

[6] Lingas (1986).

[7] Remy & Steger (2009). For earlier results on polynomial-time approximation algorithms, see Plaisted & Hong (1987) (log-factor approximation) and Levcopoulos & Krznaric (1998) (constant-factor approximation).

[8] Cheng, Golin & Tsang (1995).

[9] Lingas (1987); Heath & Pemmaraju (1994).

[10] Yang, Xu & You (1994).

[11] Keil (1994); Cheng, Golin & Tsang (1995); Cheng & Xu (2001); Hu (2010).

[12] Dickerson & Montague (1996); Cheng, Katoh & Sugai (1996); Beirouti & Snoeyink (1998); Aichholzer, Aurenhammer & Hainz (1999).

[13] Bose, Devroye & Evans (1996).

[14] Qin, Wang & Gong (1997); Capp & Julstrom (1998).

[15] Kyoda et al. (1997).

[16] Jahani, Bigham & Askari (2010).

[17] Hoffmann & Okamoto (2004); Grantson, Borgelt & Levcopoulos (2005); Knauer & Spillner (2006).

[18] Anagnostou & Corneil (1993); Meijer & Rappaport (1992).

[19] Eppstein (1994).

[20] Gudmundsson & Levcopoulos (2007); Aichholzer et al. (2009).

[21] Lenhart & Liotta (2002).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]