A quasi-polynomial time approximation scheme for minimum weight triangulation

ABSTRACT

The Minimum Weight Triangulation problem is to find a triangulation T* of minimum length for a given set of points P in the Euclidean plane. It was one of the few longstanding open problems from the famous list of twelve problems with unknown complexity status, published by Garey and Johnson [1979]. Very recently, the problem was shown to be NP-hard by Mulzer and Rote [2006]. In this article, we present a quasi-polynomial time approximation scheme for Minimum Weight Triangulation.

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: S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
• 3: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 4: Arora, S. 2003. Approximation schemes for NP-hard geometric optimization problems: A survey. Math. Prog. Ser. B 97, 43--69.
• 5: Arora, S., and Chang, K. 2004. Approximation schemes for degree-restricted MST and red-blue separation problems. Algorithmica 40, 3, 189--210.
• 6: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 7: 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]
• 8: Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 9: 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]
• 10: Gautam Das , Deborah Joseph, Which Triangulations Approximate the Complete Graph?, Proceedings of the International Symposium on Optimal Algorithms, p.168-192, May 29-June 02, 1989
• 11: Dickerson, M., Keil, J. M., and Montague, M. H. 1997. A large subgraph of the minimum weight triangulation. Disc. Computat. Geom. 18, 3, 289--304.
• 12: 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]
• 13: Düppe, R. D., and Gottschalk, H. J. 1970. Automatische Interpolation von Isolinien bei willkürlichen Stützpunken. Allgemeine Vermessungs-Nachrichten 77, 423--426.
• 14: Herbert Edelsbrunner , Tiow-Seng Tan, A quadratic time algorithm for the minmax length triangulation, SIAM Journal on Computing, v.22 n.3, p.527-551, June 1993 [doi>10.1137/0222036]
• 15: Herbert Edelsbrunner , Tiow Seng Tan , Roman Waupotitsch, An O(n2logn) time algorithm for the minmax angle triangulation, SIAM Journal on Scientific and Statistical Computing, v.13 n.4, p.994-1008, July 1992 [doi>10.1137/0913058]
• 16: Eppstein, D. 1994. Approximating the minimum weight Steiner triangulation. Disc. Comput. Geom. 11, 163--191.
• 17: 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
• 18: Gilbert, P. 1979. New results on planar triangulations. M.S. dissertation, University of Illinois.
• 19: Grantson, M., Borgelt, C., and Levcopoulos, C. 2005. Minimum weight triangulation by cutting out triangles. In Proceeding of the 16th Annual International Symposium on Algorithms and Computation. 984--994.
• 20: Joachim Gudmundsson , Christos Levcopoulos, Minimum weight pseudo-triangulations, Computational Geometry: Theory and Applications, v.38 n.3, p.139-153, October, 2007 [doi>10.1016/j.comgeo.2007.05.004]
• 21: Hoffmann, M., and Okamoto, Y. 2004. The minimum weight triangulation problem with few inner points. In Proceedings of the 1st Internation Workshop on Parameterized and Exact Computation. 200--212.
• 22: 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
• 23: Klincsek, G. 1980. Minimal triangulations of polygonal domains. Ann. Disc. Math. 9, 121--123.
• 24: 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
• 25: Christos Levcopoulos , Drago Krznaric, Quasi-greedy triangulations approximating the minimum weight triangulation, Journal of Algorithms, v.27 n.2, p.303-338, May 1, 1998 [doi>10.1006/jagm.1997.0918]
• 26: Errol Lynn Lloyd, On triangulations of a set of points in the plane, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, p.228-240, September 30-October 31, 1977
• 27: Joseph S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.402-408, January 28-30, 1996, Atlanta, Georgia, United States
• 28: Joseph S. B. Mitchell , Joseph O'Rourke, Computational geometry, ACM SIGACT News, v.32 n.3, p.63-72, 09/01/2001 [doi>10.1145/500559.500562]
• 29: Minimum weight triangulation is NP-hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137859]
• 30: David A. Plaisted , Jiarong Hong, A heuristic triangulation algorithm, Journal of Algorithms, v.8 n.5, p.405-437, Sept. 1987 [doi>10.1016/0196-6774(87)90020-4]
• 31: Michael Ian Shamos , Dan Hoey, Closest-point problems, Proceedings of the 16th Annual Symposium on Foundations of Computer Science, p.151-162, October 13-15, 1975
• 32: 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:
Minimum weight triangulation, approximation algorithms