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 |