A heuristic triangulation algorithm

1987/09/01 by David A. Plaisted, David A Plaisted, Jiarong Hong · 45 citations
Computer Science · Mathematics · #Algorithm #Bowyer–Watson algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constrained Delaunay triangulation #Delaunay triangulation #Euclidean geometry #Geometry #Heuristic #Mathematical optimization #Mathematics #Minimum-weight triangulation #Pitteway triangulation #Point set triangulation #Set (abstract data type) #Time complexity #Triangulation

paper · doi:10.1016/0196-6774(87)90020-4

published in Journal of Algorithms 8(3), 405-437 (Elsevier BV)

crossref issued 1987/09/01 · crossref published 1987/09/01 · crossref published-print 1987/09/01 · openalex publication_date 1987/09/01 · crossref created 2005/02/10 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · crossref indexed 2026/05/09 · openalex updated_date 2026/06/22

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

• Computing a subgraph of the minimum weight triangulation
• Polynomial-time instances of the minimum weight triangulation problem
• On β-skeleton as a subgraph of the minimum weight triangulation
• A lower bound for β-skeleton belonging to minimum weight triangulations☆☆This work is partially supported by NSERC grant OPG0041629.
• Implementations of the LMT heuristic for minimum weight triangulation
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Minimum-weight triangulation [wikipedia]