Removing degeneracies by perturbing the problem or perturbing the world

Pierre Alliez (1) , Olivier Devillers (1) , Jack Snoeyink (2)

1 PRISME - Geometry, Algorithms and Robotics
2 UBC-Computer Science - Computer Science Department

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.

Domaines: Géométrie algorithmique [cs.CG]

Pierre Alliez, Olivier Devillers, Jack Snoeyink. Removing degeneracies by perturbing the problem or perturbing the world. Reliable Computing, 2000, ⟨10.1023/A:1009942427413⟩. ⟨inria-00338566⟩