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
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 : vendredi 12 janvier 2018 - 11:02:31
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

  • HAL Id : inria-00338566, version 1

Collections

Citation

Pierre Alliez, Olivier Devillers, Jack Snoeyink. Removing degeneracies by perturbing the problem or perturbing the world. Reliable Computing, Springer Verlag, 2000. 〈inria-00338566〉

Partager

Métriques

Consultations de la notice

197

Téléchargements de fichiers

99