1990/01/01 by Herbert Edelsbrunner, Tiow Seng Tan, Roman Waupotitsch · 3 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Robotics and Sensor-Based Localization #3D Shape Modeling and Analysis #Triangulation #Minimax #Minimum-weight triangulation #Combinatorics #Point set triangulation #Pitteway triangulation #Algorithm #Set (abstract data type) #Mathematics #Plane (geometry) #Space (punctuation) #Computational geometry #Computer science #Delaunay triangulation #Bowyer–Watson algorithm #Mathematical optimization #Geometry
paper · pdf · doi:10.1145/98524.98535
openalex publication_date 1990/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We show 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). In the same amount of time and space we can also handle the constrained case where edges are prescribed. The algorithm iteratively improves an arbitrary initial triangulation and is fairly easy to implement.