Author(s):

Edelsbrunner, Herbert; Tan, Tiow Seng

Article 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 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 the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.

Keywords: 
computational geometry; Triangulations; Two dimensions; point sets; minmax edge length; normed metrics

Journal Title:

SIAM Journal on Computing

Volume: 
22

Issue 
3

ISSN:

00975397

Publisher:

SIAM

Date Published:

19930601

Start Page: 
527

End Page:

551

DOI: 
10.1137/0222036

Open access: 
no 