1987/10/01 by Andrzej Lingas · 34 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Robotics and Sensor-Based Localization #Advanced Image and Video Retrieval Techniques #Minimum-weight triangulation #Mathematics #Triangulation #Pitteway triangulation #Polygon (computer graphics) #Heuristic #Combinatorics #Point set triangulation #Simple polygon #Point (geometry) #Mathematical optimization #Delaunay triangulation #Set (abstract data type) #Bowyer–Watson algorithm #Discrete mathematics #Monotone polygon #Computer science #Geometry
paper · doi:10.1137/0608053
published in SIAM Journal on Algebraic and Discrete Methods 8(4), 646-658 (Society for Industrial and Applied Mathematics)
openalex publication_date 1987/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
A new heuristic for minimum weight triangulation of planar point sets is proposed. First, a polygon whose vertices are all points from the input set is constructed. Next, a minimum weight triangulation of the polygon is found by dynamic programming. The union of the polygon triangulation with the polygon yields a triangulation of the input n-point set. A nontrivial upper bound on the worst-case performance of the heuristic in terms of n and another parameter is derived. Under the assumption of uniform point distribution it is observed that the heuristic yields a solution within the factor of O(log n) from the optimum almost certainly, and the expected length of the resulting triangulation is of the same order as that of a minimum length triangulation. The heuristic runs in time O(n3 ) .