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. In 37th Annual Symposium on Foundations of Computer Science, pages 2--11, 1996.
2. S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753--782, 1998.
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. S. Arora, P. Raghavan, and S. Rao. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 106--113, 1998.
6. M. Bern and D. Eppstein. Approximation algorithms for geometric problems. In D. Hochbaum, editor, Approximation Algorithms for NP-hard Problems. PWS Publishing, 1997.
7. D. Eppstein. Approximating the minimum weight Steiner triangulation. Discrete & Computational Geometry, 11:163--191, 1994.
8. M. R. Garey and D. S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completness. 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. C. Levcopoulos and D. Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 392--401, 1996.
13. C. Levcopoulos and D. Krznaric. A near-optimal heuristic for minimum weight triangulation of convex polytops. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 519--527, 1997.
14. C. Levcopoulos and D. Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. Journal of Algorithms, 27:303--338, 1998.
15. J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple new method for the geometric k-MST problem. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 402--408, 1996.
16. W. Mulzer and G. Rote. Minimum weight triangulation is NP-hard. In Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 2006 (to appear).
17. D. A. Plaisted and J. Hong. A heuristic triangulation algorithm. Journal of Algorithms, 8:465--437, 1987.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry