Skip to Main content Skip to Navigation
New interface

Removing Degeneracies by Perturbing the Problem or the World

Pierre Alliez 1 Olivier Devillers Jack Snoeyink 
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We describe two problem-specific approaches to remove geometric degeneracies that we call {\it perturbing the problem} and {\it 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 :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:39:01 PM
Last modification on : Friday, February 4, 2022 - 3:18:26 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:44:19 PM


  • HAL Id : inria-00073373, version 1



Pierre Alliez, Olivier Devillers, Jack Snoeyink. Removing Degeneracies by Perturbing the Problem or the World. RR-3316, INRIA. 1997. ⟨inria-00073373⟩



Record views


Files downloads