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 :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073373
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 12:39:01 PM
Last modification on : Saturday, January 27, 2018 - 1:30:56 AM
Long-term archiving on : Sunday, April 4, 2010 - 11:44:19 PM

Identifiers

  • HAL Id : inria-00073373, version 1

Collections

Citation

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

Share

Metrics

Record views

210

Files downloads

355