Structural tolerance and Delaunay triangulation

In this paper we consider the tolerance of a geometric or combinatorial str ucture associated to a set of points as a measure of how much the set of po ints can be perturbed while leaving the (topological or combinatorial) stru cture essentially unchanged. We concentrate on studying the Delaunay triang ulation and show that its tolerance can be computed in O(n) time if the tri angulation is given as part of the input, while the problem has complexity Theta (n log n) if the triangulation is not known. We also study the proble m of computing the tolerance of the edges of the triangulation, and show th at the tolerance of all the edges can be computed in O(n log n) time. Final ly, we extend our study to some subgraphs of the Delaunay triangulation. (C ) 1999 Published by Elsevier Science B.V. All rights reserved.