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.
Type de document :
Rapport
RR-3316, INRIA. 1997
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00073373
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:39:01
Dernière modification le : samedi 27 janvier 2018 - 01:30:56
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:44:19

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

196

Téléchargements de fichiers

295