A note on Delaunay and optimal triangulations

1980/04/01 by David Kirkpatrick, David G. Kirkpatrick · 47 citations
Computer Science · Engineering · Mathematics · #Advanced Image and Video Retrieval Techniques #Affine combination #Affine coordinate system #Affine geometry #Affine hull #Affine shape adaptation #Affine space #Affine transformation #Bowyer–Watson algorithm #Combinatorics #Computational Geometry and Mesh Generation #Delaunay triangulation #Discrete mathematics #Mathematics #Minimum-weight triangulation #Pitteway triangulation #Pure mathematics #Robotics and Sensor-Based Localization

paper · doi:10.1016/0020-0190(80)90062-9

published in Information Processing Letters 10(3), 127-128 (Elsevier BV)

crossref issued 1980/04/01 · crossref published 1980/04/01 · crossref published-print 1980/04/01 · openalex publication_date 1980/04/01 · crossref created 2002/10/07 · crossref deposited 2019/04/09 · 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
• On triangulations of a set of points in the plane

Cited by

• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
• Approximating the minimum weight steiner triangulation
• The Greedy and Delauney triangulations are not bad in the average case
• An ω(√n) lower bound for the nonoptimality of the greedy triangulation
• New results for the minimum weight triangulation problem
• Computing the minimum weight triangulation of a set of linearly ordered points
• A heuristic triangulation algorithm
• Computing a subgraph of the minimum weight triangulation
• Polynomial-time instances of the minimum weight triangulation problem
• The drawability problem for minimum weight triangulations
• A New Heuristic for Minimum Weight Triangulation
• A genetic algorithm for the minimum weight triangulation
• An Ant Colony Algorithm for the Minimum Weight Triangulation
• Implementations of the LMT heuristic for minimum weight triangulation
• Minimum-weight triangulation [wikipedia]