A quasi-polynomial time approximation scheme for minimum weight triangulation

2009/05/01 by Jan Remy, Angelika Steger · 14 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Minimum-weight triangulation #Triangulation #Mathematics #Euclidean geometry #Point set triangulation #Scheme (mathematics) #Combinatorics #Polynomial #Set (abstract data type) #Discrete mathematics #Delaunay triangulation #Bowyer–Watson algorithm #Computer science #Geometry #Mathematical analysis

paper · doi:10.1145/1516512.1516517

published in Journal of the ACM 56(3), 1-47 (Association for Computing Machinery)

openalex publication_date 2009/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

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.

Citations

• Minimal Triangulations of Polygonal Domains
• Computing a subgraph of the minimum weight triangulation
• Closest-point problems
• Polynomial-time instances of the minimum weight triangulation problem
• An O(n² log n) Time Algorithm for the Minmax Angle Triangulation
• A heuristic triangulation algorithm
• Approximating the minimum weight steiner triangulation
• On triangulations of a set of points in the plane
• Minimum weight pseudo-triangulations
• A chain decomposition algorithm for the proof of a property on minimum weight triangulations
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation

Cited by

• Minimum-weight triangulation [wikipedia]