1992/07/01 by Herbert Edelsbrunner, Tiow Seng Tan, Roman Waupotitsch · 4 citations
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Robotics and Sensor-Based Localization #3D Shape Modeling and Analysis
paper · doi:10.1137/0913058
openalex publication_date 1992/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
It is shown that a triangulation of a set of n points in the plane that minimizes the maximum angle can be computed in time O(n2 log n) and space O(n). The algorithm is fairly easy to implement and is based on the edge-insertion scheme that iteratively improves an arbitrary initial triangulation. It can be extended to the case where edges are prescribed, and, within the same time- and space-bounds, it can lexicographically minimize the sorted angle vector if the point set is in general position. Experimental results on the efficiency of the algorithm and the quality of the triangulations obtained are included.