The Greedy and Delauney triangulations are not bad in the average case

1986/01/01 by Andrzej Lingas · 26 citations
Computer Science · Earth and Planetary Sciences · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Geological Modeling and Analysis #Greedy algorithm #Mathematics

paper · doi:10.1016/0020-0190(86)90038-4

published in Information Processing Letters 22(1), 25-31 (Elsevier BV)

crossref issued 1986/01/01 · crossref published 1986/01/01 · crossref published-print 1986/01/01 · openalex publication_date 1986/01/01 · crossref created 2003/03/14 · crossref deposited 2019/03/26 · openalex created_date 2025/10/10 · crossref indexed 2026/02/13 · openalex updated_date 2026/07/23

Citations

• Neither the greedy nor the delaunay triangulation of a planar point set approximates the optimal triangulation
• Closest-point problems
• A note on Delaunay and optimal triangulations
• On triangulations of a set of points in the plane

Cited by

• An ω(√n) lower bound for the nonoptimality of the greedy triangulation
• Computing the minimum weight triangulation of a set of linearly ordered points
• Polynomial-time instances of the minimum weight triangulation problem
• A New Heuristic for Minimum Weight Triangulation
• A genetic algorithm for the minimum weight triangulation
• Minimum-weight triangulation [wikipedia]