A quadratic time algorithm for the minmax length triangulation Conference Paper


Author(s): Edelsbrunner, Herbert; Tan, Tiow Seng
Title: A quadratic time algorithm for the minmax length triangulation
Affiliation
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(n2). 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.
Keywords: Triangulation; Mathematical Techniques - Graph Theory; Optimization
Conference Title: FOCS: Foundations of Computer Science
Conference Dates: October 1-4, 1991
Conference Location: San Juan, PR, USA
Publisher: IEEE  
Date Published: 1991-12-01
Start Page: 414
End Page: 423
DOI: 10.1109/SFCS.1991.185400
Open access: no
IST Austria Authors
Related IST Austria Work