Minimum weight triangulation is NP-hard

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: Efthymios Anagnostou , Derek Corneil, Polynomial-time instances of the minimum weight triangulation problem, Computational Geometry: Theory and Applications, v.3 n.5, p.247-259, Nov. 1993 [doi>10.1016/0925-7721(93)90016-Y ]
• 2: Ronald Beirouti , Jack Snoeyink, Implementations of the LMT heuristic for minimum weight triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.96-105, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276895]
• 3: Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 4: Patrice Belleville , Mark Keil , Michael McAllister , Jack Snoeyink, On computing edges that are in all minimum-weight triangulations, Proceedings of the twelfth annual symposium on Computational geometry, p.507-508, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237425]
• 5: Prosenjit Bose , Luc Devroye , William S. Evans, Diamonds Are Not a Minimum Weight Triangulation's Best Friend, Proceedings of the 8th Canadian Conference on Computational Geometry, p.68-73, August 12-15, 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: Siu-Wing Cheng , Naoki Katoh , Manabu Sugai, A Study of the LMT-Skeleton, Proceedings of the 7th International Symposium on Algorithms and Computation, p.256-265, December 16-18, 1996
• 8: Siu-Wing Cheng , Yin-Feng Xu, Approaching the largest &bgr;-skeleton within a minimum weight triangulation, Proceedings of the twelfth annual symposium on Computational geometry, p.196-203, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237360]
• 9: G. Das , D. Joseph, Which triangulations approximate the complete graph?, Proceedings of the international symposium on Optimal algorithms, p.168-192, November 1989, Varna, Bulgaria
• 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: R. L. Drysdale , Scott McElfresh , Jack Scott Snoeyink, On exclusion regions for optimal triangulations, Discrete Applied Mathematics, v.109 n.1-2, p.49-65, April 15, 2001 [doi>10.1016/S0166-218X(00)00236-5 ]
• 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: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 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: David S. Johnson, The NP-completeness column, ACM Transactions on Algorithms (TALG), v.1 n.1, p.160-176, July 2005 [doi>10.1145/1077464.1077476]
• 19: J. Mark Keil, Computing a subgraph of the minimum weight triangulation, Computational Geometry: Theory and Applications, v.4 n.1, p.13-26, May 1994
• 20: [20] G. T. Klincsek. Minimal triangulations of polygonal domains. Annals of Discrete Mathematics, volume 9, 1980, pp. 121-123.
• 21: Donald E. Knuth , Arvind Raghunathan, The problem of compatible representatives, SIAM Journal on Discrete Mathematics, v.5 n.3, p.422-427, Aug. 1992 [doi>10.1137/0405033]
• 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: Yoshiaki Kyoda , Keiko Imai , Fumihiko Takeuchi , Akira Tajima, A Branch-and-Cut Approach for Minimum Weight Triangulation, Proceedings of the 8th International Symposium on Algorithms and Computation, p.384-393, December 17-19, 1997
• 25: Christos Levcopoulos, An ω(√n) lower bound for the nonoptimality of the greedy triangulation, Information Processing Letters, v.25 n.4, p.247-251, June 17, 1987 [doi>10.1016/0020-0190(87)90170-0]
• 26: Christos Levcopoulos , Drago Krznaric, Quasi-greedy triangulations approximating the minimum weight triangulation, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.392-401, January 28-30, 1996, Atlanta, Georgia, United States
• 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: David A. Plaisted , Jiarong Hong, A heuristic triangulation algorithm, Journal of Algorithms, v.8 n.5, p.405-437, Sept. 1987
• 30: Jan Remy , Angelika Steger, A quasi-polynomial time approximation scheme for minimum weight triangulation, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132563]
• 31: Otfried Schwarzkopf, The extensible drawing editor Ipe, Proceedings of the eleventh annual symposium on Computational geometry, p.410-411, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220326]
• 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: Bo-Ting Yang , Yin-Feng Xu , Zhao-yong You, A Chain Decomposition Algorithm for the Proof of a Property on Minimum Weight Triangulations, Proceedings of the 5th International Symposium on Algorithms and Computation, p.423-427, August 25-27, 1994

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
PLANAR-1-IN-3-SAT, optimal triangulations