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.
273 - 277
STOC: Symposium on the Theory of Computing
Edelsbrunner H, Li X, Miller G, et al. Smoothing and cleaning up slivers. In: ACM; 2000:273-277. doi:10.1145/335305.335338
Edelsbrunner, H., Li, X., Miller, G., Stathopoulos, A., Talmor, D., Teng, S., … Walkington, N. (2000). Smoothing and cleaning up slivers (pp. 273–277). Presented at the STOC: Symposium on the Theory of Computing, ACM. https://doi.org/10.1145/335305.335338
Edelsbrunner, Herbert, Xiang Li, Gary Miller, Andreas Stathopoulos, Dafna Talmor, Shang Teng, Alper Üngör, and Noel Walkington. “Smoothing and Cleaning up Slivers,” 273–77. ACM, 2000. https://doi.org/10.1145/335305.335338.
H. Edelsbrunner et al., “Smoothing and cleaning up slivers,” presented at the STOC: Symposium on the Theory of Computing, 2000, pp. 273–277.
Edelsbrunner H, Li X, Miller G, Stathopoulos A, Talmor D, Teng S, Üngör A, Walkington N. 2000. Smoothing and cleaning up slivers. STOC: Symposium on the Theory of Computing 273–277.
Edelsbrunner, Herbert, et al. Smoothing and Cleaning up Slivers. ACM, 2000, pp. 273–77, doi:10.1145/335305.335338.
Link(s) to Main File(s)