HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Removing degeneracies by perturbing the problem or perturbing the world

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, November 13, 2008 - 4:05:25 PM
Last modification on : Friday, February 4, 2022 - 3:12:14 AM
Long-term archiving on: : Monday, June 7, 2010 - 9:24:07 PM


Files produced by the author(s)




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



Record views


Files downloads