Minimum-weight triangulation
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 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 .[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 ,[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 .[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/n2). 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)9).[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 θ = 90ª 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) + mini < k < j MWT(i,k) + MWT(k,j)
- For each possible value of j, from i + 1 to n, do:
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 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).
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.
- 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.
- 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, 1178, pp. 256–265, doi:10.1007/BFb0009502.
- 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, 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.
- 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 519066.
- 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, MR 1297812.
- 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, doi:10.1007/s10898-009-9409-z, MR 2566136.
- 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.
- Keil, J. Mark (1994), "Computing a subgraph of the minimum weight triangulation" (PDF), 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 566856.
- Klincsek, G. T. (1980), "Minimal triangulations of polygonal domains", Annals of Discrete Mathematics, 9: 121–123, doi:10.1016/s0167-5060(08)70044-x.
- 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, 4271, Berlin: Springer, pp. 49–57, doi:10.1007/11917496_5, 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, 1350, Berlin: Springer, pp. 384–393, doi:10.1007/3-540-63890-3_41, 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 896144.
- Levcopoulos, Christos (2008), "Minimum Weight Triangulation", in Kao, Ming-Yang, 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: 303–338, doi:10.1006/jagm.1997.0918, MR 1622398.
- 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 918066.
- 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 537055.
- 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. - Plaisted, D. A.; Hong, J. (1987), "A heuristic triangulation algorithm", Journal of Algorithms, 8: 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.
- Remy, Jan; Steger, Angelika (2009), "A quasi-polynomial time approximation scheme for minimum weight triangulation" (PDF), Journal of the ACM, 56 (3), Article A15, doi:10.1145/1516512.1516517.
- 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, Algorithms and Computation: 5th International Symposium, ISAAC '94, Beijing, P. R. China, August 25–27, 1994, Proceedings, Lecture Notes in Computer Science, 834, Berlin: Springer, pp. 423–427, doi:10.1007/3-540-58325-4_207, MR 1316441.