×

Removing degeneracies by perturbing the problem or perturbing the world. (English) Zbl 0996.65019

Summary: We describe two problem-specific approaches to remove geometric degeneracies that we call perturbing the problem and perturbing the world. Using as our primary examples 2-D and 3-D Delaunay triangulation with Euclidean and polygonal metrics, we show that these approaches lead to relatively simple and efficient perturbations of the points that do not depend on a fixed ordering or index. Thus, they produce canonical output, which is important for producing test suites and verifiers for randomized or dynamic geometric algorithms.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
Full Text: DOI