skip to main content
10.1145/1137856.1137859acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
Article

Minimum weight triangulation is NP-hard

Published: 05 June 2006 Publication History

Abstract

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. We use a reduction from PLANAR-1-IN-3-SAT. The correct working of the gadgets is established with computer assistance, using geometric inclusion and exclusion criteria for MWT edges, such as the diamond test and the LMT-Skeleton heuristic, as well as dynamic programming on polygonal faces.

References

[1]
{1} E. Anagnostou and D. Corneil. Polynomial time instances of the minimum weight triangulation problem. Computational Geometry: Theory and Applications 3 (1993), 247-258.
[2]
{2} R. Beirouti and J. Snoeyink. Implementations of the LMT heuristic for minimum weight triangulations. Proc. 14th Ann. Symp. Computat. Geometry, Minneapolis, pp. 96-105, 1998.
[3]
{3} M. Bern and D. Eppstein. Approximation algorithms for geometric problems in Approximation Algorithms for NP-Hard Problems, ed. D. S. Hochbaum, PWS Publishing Company, Boston, Mass., 1997, pp. 296-345.
[4]
{4} P. Belleville, M. Keil, M. McAllister, and J. Snoeyink. On computing edges that are in all minimum weight triangulations. Proceedings of the 12th Annual Symposium on Computational Geometry, Philadelphia, pp. V7-V8, 1996.
[5]
{5} P. Bose, L. Devroye, and W. Evans. Diamonds are not a minimum weight triangulation's best friends. Proceedings of the 8th Canadian Conference on Computational Geometry, Ottawa, pp. 68-73, 1996.
[6]
{6} S. W. Cheng, M. J. Golin, and J. C. F. Tsang. Expected case analysis of ß-skeletons with applications to the construction of minimum weight triangulations. Proceedings of the 8th Canadian Conference on Computational Geometry, Ottawa, pp. 279-284, 1996.
[7]
{7} S. W. Cheng, N. Katoh, and M. Sugai. A study of the LMT-skeleton. Proceedings of the 7th Annual International Symposium on Algorithms and Computation, Osaka, Japan. Springer Lecture Notes in Computer Science, volume 1178, pp. 256-265, 1996.
[8]
{8} S. W. Cheng and Y. F. Xu. Approaching the largest ß-skeleton within a minimum weight triangulation. Proceedings of the 12th Annual Symposium on Computational Geometry, Philadelphia, Pennsylvania, pp. 196-203, 1996.
[9]
{9} G. Das and D. Joseph. Which triangulations approximate the complete graph. Proceedings of the International Symposium on Optimal Algorithms, Varna, Bulgaria. Springer Lecture Notes in Computer Science, volume 401, pp. 168-192, 1989.
[10]
{10} M. T. Dickerson, J. M. Keil, and M. H. Montague. A large subgraph of the minimum weight triangulation. Discrete and Computational Geometry 18 (1997), 289-304.
[11]
{11} R. L. Drysdale, S. A. McElfresh, and J. Snoeyink. On exclusion regions for optimal triangulations. Discrete Applied Mathematics 109 (2001), 49-65.
[12]
{12} R. L. Drysdale, G. Rote, and O. Aichholzer. A simple linear time greedy triangulation algorithm for uniformly distributed points. IIG-Report-Series 408, Technische Universität Graz, 1995.
[13]
{13} R. D. Duppe and H. J. Gottschalk. Automatische Interpolation von Isolinien bei willkürlichen Stützpunkten. Allgemeine Vermessungsnachrichten 77 (1970), 423-426.
[14]
{14} M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, New York, 1979.
[15]
{15} P. D. Gilbert. New results in planar triangulations. Report R-850, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, 1979.
[16]
{16} R. Hainz, O. Aichholzer, and F. Aurenhammer. New results on minimum weight triangulations and the LMT-skeleton. Proceedings of the 13th European Workshop on Computational Geometry, Würzburg, Germany, pp. 4-6, 1997.
[17]
{17} M. Hoffmann and Y. Okamoto. The minimum weight triangulation problem with few interior points. Proceedings of the International Workshop on Parameterized and Exact Computation, Bergen, Norway, Springer Lecture Notes in Computer Science, volume 3162, pp. 200-212, 2004.
[18]
{18} D. Johnson. The NP-completeness column. ACM Trans. Algorithms 1 (2005), 160-176.
[19]
{19} J. M. Keil. Computing a subgraph of the minimum weight triangulation. Computational Geometry: Theory and Applications 4 (1994), 13-26.
[20]
{20} G. T. Klincsek. Minimal triangulations of polygonal domains. Annals of Discrete Mathematics, volume 9, 1980, pp. 121-123.
[21]
{21} D. E. Knuth and A. Raghunathan. The problem of compatible representatives. SIAM Journal on Discrete Mathematics 5 (1992), 422-427.
[22]
{22} D. Lichtenstein. Planar formulae and their uses. SIAM J. Computing 11 (1982), 329-343.
[23]
{23} D. G. Kirkpatrick. A note on Delaunay and optimal triangulations. Information Processing Letters 10 (1980), 127-128.
[24]
{24} Y. Kyoda, K. Imai, F. Takeuchi, and A. Tajima. A branch-and-cut approach for minimum weight triangulation. Proceedings of the 8th International Symposium on Algorithms and Computation, Singapore. Springer Lecture Notes in Computer Science, volume 1350, pp. 384-393, 1997.
[25]
{25} C. Levcopoulos. An ¿ (¿n) lower bound for the nonoptimality of the greedy triangulation. Information Processing Letters 25 (1987), 247-251.
[26]
{26} C. Levcopoulos and D. Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, Georgia, 1996, pp. 392-401.
[27]
{27} E. L. Lloyd. On triangulations of a set of points in the plane. Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science, Providence, Rhode Island, pp. 228-240, 1977.
[28]
{28} G. K. Manacher and A. L. Zobrist. Neither the greedy nor the the Delaunay triangulation approximates the optimum. Information Processing Letters 9 (1979), 31-34.
[29]
{29} D. A. Plaisted and J. Hong. A heuristic triangulation algorithm. Journal of Algorithms 8 (1987), 405-437.
[30]
{30} J. Remy and A Steger. A quasi-polynomial time approximation scheme for minimum weight triangulation. Proceedings of the 38th ACM Symposium on Theory of Computing, Seattle, Washington, 2006.
[31]
{31} O. Schwarzkopf. The extensible drawing editor Ipe. Proceedings of the 11th Annual Symposium on Computational Geometry, Vancouver, British Columbia, pp. 410-411, 1995.
[32]
{32} M. I. Shamos and D. Hoey. Closest point problems. Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, California, pp. 151-162, 1975.
[33]
{33} B. T. Yang, Y. F. Xu, and Z. Y. You. A chain decomposition algorithm for the proof of a property on minimum weight triangulations. Proceedings of the 5th Annual International Symposium on Algorithms and Computation, Beijing, China. Springer Lecture Notes in Computer Science, volume 834, pp. 423-427, 1994.

Cited By

View all
  • (2018)A Multi-Institutional Perspective on H/FOSS Projects in the Computing CurriculumACM Transactions on Computing Education10.1145/314547618:2(1-31)Online publication date: 11-Jul-2018
  • (2018)Software Theater—Teaching Demo-Oriented PrototypingACM Transactions on Computing Education10.1145/314545418:2(1-30)Online publication date: 11-Jul-2018
  • (2011)Beyond triangulationProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033210(231-242)Online publication date: 15-Aug-2011
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry
June 2006
500 pages
ISBN:1595933409
DOI:10.1145/1137856
  • Program Chairs:
  • Nina Amenta,
  • Otfried Cheong
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. PLANAR-1-IN-3-SAT
  2. optimal triangulations

Qualifiers

  • Article

Conference

SoCG06

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)2
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)A Multi-Institutional Perspective on H/FOSS Projects in the Computing CurriculumACM Transactions on Computing Education10.1145/314547618:2(1-31)Online publication date: 11-Jul-2018
  • (2018)Software Theater—Teaching Demo-Oriented PrototypingACM Transactions on Computing Education10.1145/314545418:2(1-30)Online publication date: 11-Jul-2018
  • (2011)Beyond triangulationProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033210(231-242)Online publication date: 15-Aug-2011
  • (2010)Inapproximability for planar embedding problemsProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873621(222-235)Online publication date: 17-Jan-2010
  • (2010)Technical SectionComputers and Graphics10.1016/j.cag.2010.01.00134:2(125-135)Online publication date: 1-Apr-2010
  • (2009)Improved bounds on the average length of longest common subsequencesJournal of the ACM10.1145/1516512.151651956:3(1-38)Online publication date: 19-May-2009
  • (2009)Adding nesting structure to wordsJournal of the ACM10.1145/1516512.151651856:3(1-43)Online publication date: 19-May-2009
  • (2009)A quasi-polynomial time approximation scheme for minimum weight triangulationJournal of the ACM10.1145/1516512.151651756:3(1-47)Online publication date: 19-May-2009
  • (2008)Optimal higher order Delaunay triangulations of polygonsProceedings of the 8th Latin American conference on Theoretical informatics10.5555/1792918.1792930(133-145)Online publication date: 7-Apr-2008
  • (2008)Minimum weight convex Steiner partitionsProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347147(581-590)Online publication date: 20-Jan-2008
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media