A Simple Method for Resolving Degeneracies in Delaunay Triangulations


M.B. Dillencourt, University of California;W.D. Smith, NECI

                  01/20/93

ABSTRACT:
 We characterize the conditions under which completing a Delaunay
 tessellation produces a configuration which is a nondegenerate Delaunay
 triangulation of an arbitrarily small perturbation of the original sites. One
 consequence of this result is s simple method for resolving degeneracies in
 Delaunay triangulations that does not require symbolic perturbation of the
 data.

  KEYWORDS:
 DELAUNAY TRIANGULATIONS, INSCRIBABLE GRAPHS,
 PERTURBATIONS, DEGENERACIES, GRAPH-THEORETIC
 CHARACTERIZATION, FINITE PRECISION, CALCULATION,
 NUMERICAL ROBUSTNESS