28562 articles – 22061 Notices  [english version]

inria-00073373, version 1

Removing Degeneracies by Perturbing the Problem or the World

Pierre Alliez () 1, Olivier Devillers (), Jack Snoeyink

N° RR-3316 (1997)

Résumé : 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.

  • 1 :  PRISME (INRIA Sophia Antipolis)
  • INRIA
  • Domaine : Informatique/Autre
  • Mots-clés : COMPUTATIONAL GEOMETRY / GEOMETRIC COMPUTING / DELAUNAY TRIANGULATIONCOMPUTATIONAL GEOMETRY / GEOMETRIC COMPUTING / DELAUNAY TRIANGULATION
  • Référence interne : RR-3316
 
  • inria-00073373, version 1
  • http://hal.inria.fr/inria-00073373
  • oai:hal.inria.fr:inria-00073373
  • Contributeur : Rapport De Recherche Inria <>
  • Soumis le : Mercredi 24 Mai 2006, 12:39:01
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:27