Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation

1998/05/01 by Christos Levcopoulos, Drago Krznaric · 36 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Constrained Delaunay triangulation #Delaunay triangulation #Discrete mathematics #Geometry #Greedy algorithm #Mathematics #Minimum weight #Minimum-weight triangulation #Pitteway triangulation #Point set triangulation #Triangulation

paper · doi:10.1006/jagm.1997.0918

published in Journal of Algorithms 27(2), 303-338 (Elsevier BV)

crossref issued 1998/05/01 · crossref published 1998/05/01 · crossref published-print 1998/05/01 · openalex publication_date 1998/05/01 · crossref created 2002/10/06 · crossref deposited 2024/12/02 · openalex created_date 2025/10/10 · crossref indexed 2025/11/08 · openalex updated_date 2026/07/29

Citations

• Neither the greedy nor the delaunay triangulation of a planar point set approximates the optimal triangulation
• New results for the minimum weight triangulation problem
• An ω(√n) lower bound for the nonoptimality of the greedy triangulation
• Approximating the minimum weight steiner triangulation
• A note on Delaunay and optimal triangulations

Cited by

• A new asymmetric inclusion region for minimum weight triangulation
• Minimum weight pseudo-triangulations
• A lower bound for β-skeleton belonging to minimum weight triangulations☆☆This work is partially supported by NSERC grant OPG0041629.
• The drawability problem for minimum weight triangulations
• On minimum weight pseudo-triangulations
• Implementations of the LMT heuristic for minimum weight triangulation
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Minimum-weight triangulation [wikipedia]