Implementations of the LMT heuristic for minimum weight triangulation

1998/01/01 by Ronald Beirouti, Jack Snoeyink · 34 citations
Computer Science · Engineering · #Computational Geometry and Mesh Generation #3D Modeling in Geospatial Applications #3D Shape Modeling and Analysis #Citation #Triangulation #Computer science #Implementation #Heuristic #Library science #Software engineering #Artificial intelligence #Geography #Cartography

paper · pdf · doi:10.1145/276884.276895

openalex publication_date 1998/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

No polynomial-time algorithm is kno-ivn to compute t,he minimum weight triangulation (MWT) of a finite planar point set. In this paper xve present efficient implementat,ions of the LMT-skeleton heurist'ic, xvhich identifies edges that must be, and cannot be, in an MWT. For uniformly distributed points, v:e can compute the esact MWT of tens of thousands of points in minutes.

Citations

• Minimal Triangulations of Polygonal Domains
• A (usually?) connected subgraph of the minimum weight triangulation
• Computing a subgraph of the minimum weight triangulation
• Polynomial-time instances of the minimum weight triangulation problem
• An ω(√n) lower bound for the nonoptimality of the greedy triangulation
• A heuristic triangulation algorithm
• A note on Delaunay and optimal triangulations
• On triangulations of a set of points in the plane
• A chain decomposition algorithm for the proof of a property on minimum weight triangulations
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation

Cited by

• Optimal and suboptimal robust algorithms for proximity graphs
• Minimum-weight triangulation [wikipedia]