inria-00338566, version 1
Removing degeneracies by perturbing the problem or perturbing the world
Pierre Alliez
1Olivier Devillers
1Jack Snoeyink 2
Reliable Computing (2000)
Résumé : 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.
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- 2 : Computer Science
- University of British Columbia
- Domaine : Informatique/Géométrie algorithmique
- inria-00338566, version 1
- http://hal.inria.fr/inria-00338566
- oai:hal.inria.fr:inria-00338566
- Contributeur : Olivier Devillers
- Soumis le : Jeudi 13 Novembre 2008, 16:05:25
- Dernière modification le : Jeudi 13 Novembre 2008, 16:34:52






Documents associés
Exporter