A quadratic time algorithm for the minmax length triangulation

2002/12/09 by H. Edelsbruneer, T.S. Tan · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Numerical Analysis Techniques #Computer Graphics and Visualization Techniques #Minimax #Triangulation #Combinatorics #Point set triangulation #Mathematics #Quadratic equation #Set (abstract data type) #Algorithm #Minimum-weight triangulation #Enhanced Data Rates for GSM Evolution #Graph #Computer science #Discrete mathematics #Mathematical optimization #Artificial intelligence #Delaunay triangulation #Geometry #Constrained Delaunay triangulation

paper · doi:10.1109/sfcs.1991.185400

openalex publication_date 2002/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time O(n/sup 2/). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.>

Citations

• An O(n² log n) Time Algorithm for the Minmax Angle Triangulation
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• An O(n2log n) time algorithm for the MinMax angle triangulation
• On triangulations of a set of points in the plane

Cited by

• Relative neighborhood graphs and their relatives
• Point-set triangulation [wikipedia]