Wolfgang Mulzer
Skip Abstract Section
Skip Supplemental Material SectionAbstract
A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We prove that the decision version of this problem is NP-hard, using a reduction from PLANAR 1-IN-3-SAT. The correct working of the gadgets is established with computer assistance, using dynamic programming on polygonal faces, as well as the β-skeleton heuristic to certify that certain edges belong to the minimum-weight triangulation.
Supplemental Material
Available for Download
txt
all-coordinates.txt (59.1 KB)
Precise description of the point sets that were used for the gadgets described in the article (unrefereed material)
pdf
mwt_tr.pdf (746.8 KB)
Extended version of the article with a technical appendix that includes the data for all gadgets and documents the computer program; also available under http://arxiv.org/abs/cs/0601002 (unrefereed material)
zip
python-programs.zip (42.6 KB)
Source code for a Python program that verifies that the gadgets fulfill the desired properties (unrefereed material)
- Aichholzer, O., Aurenhammer, F., and Hainz, R. 1999. New results on MWT subgraphs. Inf. Proc. Lett. 69, 5, 215--219. Google Scholar
Digital Library
- Anagnostou, E., and Corneil, D. 1993. Polynomial-time instances of the minimum weight triangulation problem. Comput. Geom. Theory Appl. 3, 5, 247--259. Google ScholarDigital Library
- Beirouti, R., and Snoeyink, J. 1998. Implementations of the LMT heuristic for minimum weight triangulation. In SCG'98: Proceedings of the 14th Annual Symposium on Computational Geometry. ACM, New York, 96--105. Google ScholarDigital Library
- Belleville, P., Keil, M., McAllister, M., and Snoeyink, J. 1996. On computing edges that are in all minimum-weight triangulations. In SCG'96: Proceedings of the 12th Annual Symposium on Computational Geometry. ACM, New York, 507--508. Google ScholarDigital Library
- Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., and Tan, T. S. 1993. Edge insertion for optimal triangulations. Discrete Comput. Geom. 10, 1, 47--65.Google ScholarDigital Library
- Bern, M. W., and Eppstein, D. 1992. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry, D.-Z. Du and F. K.-M. Hwang, Eds. Number 1 in Lecture Notes Series on Computing. World Scientific, River Edge, NJ, 23--90.Google Scholar
- Bern, M. W., and Eppstein, D. 1996. Approximation algorithms for geometric problems. In Approximation Algorithms for NP-hard Problems, D. Hochbaum, Ed. PWS Publishing, Boston, MA, Chap. 8, 296--345. Google ScholarDigital Library
- Blömer, J. 1991. Computing sums of radicals in polynomial time. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 670--677. Google ScholarDigital Library
- Bose, P., Devroye, L., and Evans, W. S. 2002. Diamonds are not a minimum weight triangulation's best friend. Int. J. Comput. Geom. Appl. 12, 6, 445--454.Google ScholarCross Ref
- Cheng, S.-W., Golin, M., and Tsang, J. 1995. Expected case analysis of β-skeletons with applications to the construction of minimum-weight triangulations. In Proceedings of the 7th Canadian Conference on Computational Geometry (Quebec City, Que., Canada). 279--284.Google Scholar
- Cheng, S.-W., Katoh, N., and Sugai, M. 1996. A study of the LMT-skeleton. In ISAAC '96: Proceedings of the 7th International Symposium on Algorithms and Computation (Osaka, Japan). Lecture Notes in Computer Science, vol. 1178. Springer-Verlag, New York, 256--265. Google ScholarDigital Library
- Cheng, S.-W., and Xu, Y.-F. 1996. Approaching the largest β-skeleton within a minimum weight triangulation. In SCG'96: Proceedings of the 12th Annual Symposium on Computational geometry. ACM, New York, 196--203. Google ScholarDigital Library
- Das, G., and Joseph, D. 1989. Which triangulations approximate the complete graph? In Proceedings of the International Symposium on Optimal Algorithms. Lecture Notes in Computer Science, vol. 401. Springer-Verlag, New York, 168--192. Google ScholarDigital Library
- de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 2000. Computational Geometry: Algorithms and Applications, 2 ed. Springer Verlag, Berlin, Heidelberg, New York. Google ScholarDigital Library
- Dickerson, M. T., Keil, J. M., and Montague, M. H. 1997. A large subgraph of the minimum weight triangulation. Disc. Comput. Geom. 18, 3, 289--304.Google ScholarCross Ref
- Drysdale, R., Rote, G., and Aichholzer, O. 1995. A simple linear time greedy triangulation algorithm for uniformly distributed points. Tech. Rep. IIG-408, Institute for Information Processing, Technische Universität Graz.Google Scholar
- Drysdale, R. L., McElfresh, S., and Snoeyink, J. S. 2001. On exclusion regions for optimal triangulations. Disc. Appl. Math. 109, 1-2, 49--65. Google ScholarDigital Library
- Düppe, R.-D., and Gottschalk, H.-J. 1970. Automatische Interpolation von Isolinien bei willkürlich verteilten Stützpunkten. Allgemeine Vermessungs-Nachrichten 77, 10, 423--426.Google Scholar
- Edelsbrunner, H., Tan, T. S., and Waupotitsch, R. 1992. An O(n2log n) time algorithm for the minmax angle triangulation. SIAM J. Sci. Statist. Comput. 13, 4, 994--1008. Google ScholarDigital Library
- Eppstein, D. 1994. Approximating the minimum weight Steiner triangulation. Disc. Comput. Geometry 11, 2, 163--191.Google ScholarDigital Library
- Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York. Google ScholarDigital Library
- Gilbert, P. D. 1979. New results in planar triangulations. Tech. Rep. R--850, Univ. Illinois Coordinated Science Lab.Google Scholar
- Hoffmann, M., and Okamoto, Y. 2006. The minimum weight triangulation problem with few inner points. Comput. Geom. Theory Appl. 34, 3, 149--158. Google ScholarDigital Library
- Johnson, D. S. 2005. The NP-completeness column. ACM Trans. Algorithms 1, 1, 160--176. Google ScholarDigital Library
- Keil, J. M. 1994. Computing a subgraph of the minimum weight triangulation. Comput. Geom. Theory Appl. 4, 1, 13--26. Google ScholarDigital Library
- Kellerer, H., Pferschy, U., and Pisinger, D. 2007. Knapsack Problems. Springer-Verlag, Berlin, Germany.Google Scholar
- Kirkpatrick, D. G. 1980. A note on Delaunay and optimal triangulations. Inf. Process. Lett. 10, 3, 127--128.Google ScholarCross Ref
- Klincsek, G. T. 1980. Minimal triangulations of polygonal domains. In Combinatorics 79 (Proc. Colloq., Univ. Montréal, 1979), Part II, M. Deza and I. G. Rosenberg, Eds. Ann. Discrete Math. 9, 121--123.Google Scholar
- Knuth, D. E., and Raghunathan, A. 1992. The problem of compatible representatives. SIAM J. Disc. Math. 5, 3, 422--427. Google ScholarDigital Library
- Kyoda, Y., Imai, K., Takeuchi, F., and Tajima, A. 1997. A branch-and-cut approach for minimum weight triangulation. In ISAAC '97: Proceedings of the 8th International Symposium on Algorithms and Computation (Singapore). Lecture Notes in Computer Science, vol. 1350. Springer-Verlag, New York, 384--393. Google ScholarDigital Library
- Levcopoulos, C. 1987. An Ω(&sqrt;n) lower bound for the nonoptimality of the greedy triangulation. Inf. Process. Lett. 25, 4, 247--251. Google ScholarDigital Library
- Levcopoulos, C., and Krznaric, D. 1996. Quasi-greedy triangulations approximating the minimum weight triangulation. In SODA '96: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 392--401. Google ScholarDigital Library
- Lichtenstein, D. 1982. Planar formulae and their uses. SIAM J. Comput. 11, 2, 329--343.Google ScholarDigital Library
- Lloyd, E. L. 1977. On triangulations of a set of points in the plane. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (Providence, R.I.). IEEE Computer Society, Press, Los Alamitos, CA, 228--240.Google ScholarDigital Library
- Manacher, G. K., and Zobrist, A. L. 1979. Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation. Inf. Process. Lett. 9, 1, 31--34.Google ScholarCross Ref
- Mulzer, W., and Rote, G. 2006. Minimum weight triangulation is NP-hard. In SCG '06: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry. ACM, New York, 1--10. Google ScholarDigital Library
- Mulzer, W., and Rote, G. 2007. Minimum-weight triangulation is NP-hard. Tech. Rep. B05-23 (revised), Sept. 2007, Freie Universität Berlin, Institut für Informatik. arXiv:cs/0601002.Google Scholar
- Plaisted, D. A., and Hong, J. 1987. A heuristic triangulation algorithm. J. Algorithms 8, 5, 405--437. Google ScholarDigital Library
- Remy, J., and Steger, A. 2006. A quasi-polynomial time approximation scheme for minimum weight triangulation. In STOC '06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM Press, New York, 316--325. Google ScholarDigital Library
- Schaefer, T. J. 1978. The complexity of satisfiability problems. In STOC '78: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. ACM, New York, 216--226. Google ScholarDigital Library
- Schwarzkopf, O. 1995. The extensible drawing editor Ipe. In SCG '95: Proceedings of the Eleventh Annual Symposium on Computational Geometry. ACM, New York, 410--411. Google ScholarDigital Library
- Shamos, M. I., and Hoey, D. 1975. Closest-point problems. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 151--162.Google Scholar
- Wang, C. A., and Yang, B. 2001. A lower bound for β-skeleton belonging to minimum weight triangulations. Comput. Geom. Theory Appl. 19, 1, 35--46. Google ScholarDigital Library
- Yang, B.-T., Xu, Y.-F., and You, Z. 1994. A chain decomposition algorithm for the proof of a property on minimum weight triangulations. In ISAAC '94: Proceedings of the 5th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 834. Springer-Verlag, New York, 423--427. Google ScholarDigital Library
Index Terms
- Minimum-weight triangulation is NP-hard
Recommendations
Minimum weight triangulation is NP-hard
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometryA triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We ...
New results for the minimum weight triangulation problem
Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is ...
Approximating the minimum weight triangulation
SODA '92: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithmsIn O(n log n) time we compute a triangulation with O(n) new points, and no obtuse triangles, that has length within a constant factor of the minimum possible. We also approximate the minimum weight Steiner triangulation using triangulations with no ...
Comments