Polynomial-time instances of the minimum weight triangulation problem

1993/11/01 by Efthymios Anagnostou, Derek G. Corneil, Derek Corneil · 21 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Bowyer–Watson algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Convex hull #Delaunay triangulation #Discrete mathematics #Geometry #Heuristics #Mathematical optimization #Mathematics #Minimum-weight triangulation #Optimization and Packing Problems #Point set triangulation #Polygon (computer graphics) #Polynomial #Regular polygon #Set (abstract data type) #Time complexity #Triangulation

paper · pdf · doi:10.1016/0925-7721(93)90016-y

published in Computational Geometry 3(5), 247-259 (Elsevier BV)

crossref issued 1993/11/01 · crossref published 1993/11/01 · crossref published-print 1993/11/01 · openalex publication_date 1993/11/01 · crossref created 2002/07/26 · crossref deposited 2020/02/05 · crossref indexed 2025/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Citations

• Minimal Triangulations of Polygonal Domains
• Neither the greedy nor the delaunay triangulation of a planar point set approximates the optimal triangulation
• Closest-point problems
• An O(n² log n) Time Algorithm for the Minmax Angle Triangulation
• An ω(√n) lower bound for the nonoptimality of the greedy triangulation
• A heuristic triangulation algorithm
• An O(n2log n) time algorithm for the MinMax angle triangulation
• A note on Delaunay and optimal triangulations
• On triangulations of a set of points in the plane
• The Greedy and Delauney triangulations are not bad in the average case
• A quadratic time algorithm for the minmax length triangulation

Cited by

• A lower bound for β-skeleton belonging to minimum weight triangulations☆☆This work is partially supported by NSERC grant OPG0041629.
• An Ant Colony Algorithm for the Minimum Weight Triangulation
• Implementations of the LMT heuristic for minimum weight triangulation
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Minimum-weight triangulation [wikipedia]