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 [8] in 1979. Very recently the problem was shown to be NP-hard by Mulzer and Rote. In this paper, we present a quasi-polynomial time approximation scheme for MINIMUM WEIGHT TRIANGULATION.

REFERENCES

• 1: 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
• 2: 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]
• 3: S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey. Mathematical Programming, Series B, 97:43--69, 2003.
• 4: S. Arora and K. Chang. Approximation schemes for degree-restricted MST and red-blue separation problems. Algorithmica, 40(3):189--210, 2004.
• 5: 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]
• 6: Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 7: D. Eppstein. Approximating the minimum weight Steiner triangulation. Discrete & Computational Geometry, 11:163--191, 1994.
• 8: 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
• 9: P. Gilbert. New results on planar triangulations. Master's thesis, University of Illinois, 1979.
• 10: J. Gudmundsson and C. Levcopoulos. Minimum weight pseudo-triangulations. In Proceedings of the 20th European Workshop on Computational Geometry, 2004.
• 11: G. Klincsek. Minimal triangulations of polygonal domains. Annals of Discrete Mathemathics, 9:121--123, 1980.
• 12: 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
• 13: Christos Levcopoulos , Drago Krznaric, A near-optimal heuristic for minimum weight triangulation of convex polygons, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.518-527, January 05-07, 1997, New Orleans, Louisiana, United States
• 14: 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]
• 15: 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
• 16: 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]
• 17: 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]

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:
approximation algorithms, minimum weight triangulation