Jan Remy
Skip Abstract Section
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.
- Anagnostou, E., and Corneil, D. G. 1993. Polynomial-time instances of the minimum weight triangulation problem. Computat. Geom. Theory Applic. 3, 247--259. Google Scholar
Digital Library
- Arora, S. 1996. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 2--11. Google ScholarDigital Library
- Arora, S. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5, 753--782. Google ScholarDigital Library
- Arora, S. 2003. Approximation schemes for NP-hard geometric optimization problems: A survey. Math. Prog. Ser. B 97, 43--69.Google ScholarCross Ref
- Arora, S., and Chang, K. 2004. Approximation schemes for degree-restricted MST and red-blue separation problems. Algorithmica 40, 3, 189--210.Google ScholarCross Ref
- Arora, S., Raghavan, P., and Rao, S. 1998. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, New York, 106--113. Google ScholarDigital Library
- Belleville, P., Keil, J. M., McAllister, M., and Snoeyink, J. 1996. On computing edges that are in all minimum-weight triangulations. In Proceedings of the 12th Annual Symposium on Computational Geometry. V7--V8. Google ScholarDigital Library
- Bern, M., and Eppstein, D. 1997. Approximation algorithms for geometric problems. In Approximation Algorithms for NP-hard Problems, D. Hochbaum, Ed. PWS Publishing. Google ScholarDigital Library
- Cheng, S.-W., and Xu, Y.-F. 1996. Approaching the largest beta-skeleton within a minimum weight triangulation. In Proceedings of the 12th Annual Symposium on Computational Geometry. 196--203. Google ScholarDigital Library
- Das, G., and Joseph, D. 1989. Which triangulations approximate the complete graph?. In Proceedings of the International Symposium on Optimal Algorithms, 168--192. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Drysdale, R. L., McElfresh, S. A., and Snoeyink, J. 2001. On exclusion regions for optimal triangulations. Disc. Appl. Math. 109, 1-2, 49--65. Google ScholarDigital Library
- Düppe, R. D., and Gottschalk, H. J. 1970. Automatische Interpolation von Isolinien bei willkürlichen Stützpunken. Allgemeine Vermessungs-Nachrichten 77, 423--426.Google Scholar
- Edelsbrunner, H., and Tan, T. S. 1993. A quadratic time algorithm for the minmax length triangulation. SIAM J. Comput. 22, 3, 527--551. Google ScholarDigital Library
- Edelsbrunner, H., Tan, T. S., and Waupotitsch, R. 1992. An O(n2 log n) time algorithm for the minmax angle triangulation. SIAM J. Sci. Comput. 13, 4. Google ScholarDigital Library
- Eppstein, D. 1994. Approximating the minimum weight Steiner triangulation. Disc. Comput. Geom. 11, 163--191.Google ScholarDigital Library
- Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability---A Guide to the Theory of NP-Completness. Google ScholarDigital Library
- Gilbert, P. 1979. New results on planar triangulations. M.S. dissertation, University of Illinois.Google Scholar
- 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. Google ScholarDigital Library
- Gudmundsson, J., and Levcopoulos, C. 2007. Minimum weight pseudo-triangulations. Computat. at Geom. Theory Appl. 38, 139--153. Google ScholarDigital Library
- 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.Google Scholar
- Keil, J. M. 1994. Computing a subgraph of the minimum weight triangulation. Computat. Geom. Theory Applic. 4, 18--26. Google ScholarDigital Library
- Klincsek, G. 1980. Minimal triangulations of polygonal domains. Ann. Disc. Math. 9, 121--123.Google ScholarCross Ref
- Levcopoulos, C., and Krznaric, D. 1996. Quasi-greedy triangulations approximating the minimum weight triangulation. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 392--401. Google ScholarDigital Library
- Levcopoulos, C., and Krznaric, D. 1998. Quasi-greedy triangulations approximating the minimum weight triangulation. J. Algorithms 27, 303--338. Google ScholarDigital Library
- Lloyd, E. 1977. On triangulations of a set of points in the plane. In Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 228--240. Google ScholarDigital Library
- Mitchell, J. S. B. 1996. 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, ACM, New York, 402--408. Google ScholarDigital Library
- Mitchell, J. S. B., and O'Rourke, J. 2001. Computational Geometry Column 42. SIGACT News 32, 3, 63--72. Google ScholarDigital Library
- Mulzer, W., and Rote, G. 2006. Minimum weight triangulation is NP-hard. In Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, ACM, New York, 1--10. Google ScholarDigital Library
- Plaisted, D. A., and Hong, J. 1987. A heuristic triangulation algorithm. Journal of Algorithms 8, 465--437. Google ScholarDigital Library
- Shamos, M. I., and Hoey, D. J. 1975. Closest-point problems. In Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 151--162. Google ScholarDigital Library
- Yang, B. T., Xu, Y. F., and You, Z. Y. 1994. A chain decomposition algorithm for the proof of a property on minimum weight triangulations. In Proceedings of the 5th International Symposium on Algorithms and Computation. 423--427. Google ScholarDigital Library
Index Terms
- A quasi-polynomial time approximation scheme for minimum weight triangulation
Recommendations
A quasi-polynomial time approximation scheme for minimum weight triangulation
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingThe 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 ...
New results for the minimum weight triangulation problem
Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is ...
A parallel approximation algorithm for minimum weight triangulation
In this paper we show a parallel algorithm that produces a triangulation which is within a constant factor longer than the Minimum Weight Triangulation (MWT) in time O(log n) using O(n) processors and linear space in the CRCW PRAM model. We present a ...
Comments