Smoothing and Cleaning up Slivers

Herbert Edelsbruner
Department of Computer Science
Duke University

Xiang-Yang Li
Department of Computer Science
Universit of Illinois at Urbana-Champaign

Gary Miller
Department of Computer Science
Carnegie Mellon University

Andreas Stathopoulos
Department of Computer Science
College of William and Mary

Dafna Talmor
LMS-CADSI

Shang-Hua Teng
Department of Computer Science
University of Illinois at Urbana-Champaign

Alper Üngör
Department of Computer Science
University of Illinois at Urbana-Champaign

Noel Walkington
Department of Mathematical Sciences
Carnegie Mellon University

ABSTRACT: A sliver is a tetrahedron whose four vertices lie close to a plane and whose perpendicular projection to that plane is a convex quadrilateral with no short edge. Slivers are both undesirable and ubiquitous in 3-dimensional Delaunay trangulations. Even when the point-set is well-spaced, slivers may result. This paper shows that such a point set permits a small perturbation whose Delaunay triangulation contains no slivers. It also gives deterministic algorithms that compute the perturbation of n points in time $O(n \log n)$ with one processor and in time $O(\log n)$ with O(n) processors.