TY - CONF
AB - 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 triangulations. 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.
AU - Edelsbrunner, Herbert
AU - Li, Xiang
AU - Miller, Gary
AU - Stathopoulos, Andreas
AU - Talmor, Dafna
AU - Teng, Shang
AU - Üngör, Alper
AU - Walkington, Noel
ID - 3555
SN - 9781581131840
T2 - Proceedings of the 32nd annual ACM symposium on Theory of computing
TI - Smoothing and cleaning up slivers
ER -