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.
Type de document :
Article dans une revue
Reliable Computing, Springer Verlag, 2000, 〈10.1023/A:1009942427413〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00338566
Contributeur : Olivier Devillers <>
Soumis le : jeudi 13 novembre 2008 - 16:05:25
Dernière modification le : mercredi 7 mars 2018 - 10:37:26
Document(s) archivé(s) le : lundi 7 juin 2010 - 21:24:07

Fichier

ads-rdppw-00.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

218

Téléchargements de fichiers

114