TY - JOUR
AB - 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.
AU - Edelsbrunner, Herbert
AU - Tan, Tiow
ID - 4042
IS - 3
JF - SIAM Journal on Computing
SN - 0097-5397
TI - A quadratic time algorithm for the minmax length triangulation
VL - 22
ER -