A QUADRATIC TIME ALGORITHM FOR THE MINMAX LENGTH TRIANGULATION

Authors
EDELSBRUNNER H TAN TS
Citation
H. Edelsbrunner et Ts. Tan, A QUADRATIC TIME ALGORITHM FOR THE MINMAX LENGTH TRIANGULATION, SIAM journal on computing, 22(3), 1993, pp. 527-551
Citations number
27
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
22
Issue
3
Year of publication
1993
Pages
527 - 551
Database
ISI
SICI code
0097-5397(1993)22:3<527:AQTAFT>2.0.ZU;2-T
Abstract
It is shown that a triangulation of a set of n points in the plane tha t minimizes the maximum edge length can be computed in time 0(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 t he relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.