inria-00073373, version 1

Removing Degeneracies by Perturbing the Problem or the World

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

N° RR-3316 (1997)

• 1:  PRISME (INRIA Sophia Antipolis)
• 
  INRIA France

Bibliographic reference

• Type of document: Research reports
• Domain: Computer Science/Other
• Title: Removing Degeneracies by Perturbing the Problem or the World
• 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.
• Full text language: English
• Publication date: 1997-12
• Keywords: COMPUTATIONAL GEOMETRY / GEOMETRIC COMPUTING / DELAUNAY TRIANGULATIONCOMPUTATIONAL GEOMETRY / GEOMETRIC COMPUTING / DELAUNAY TRIANGULATION
• Writing date: 1997-12
• Internal note: RR-3316

Attached file list to this document: 

• inria-00073373, version 1
• http://hal.inria.fr/inria-00073373
• oai:hal.inria.fr:inria-00073373
• From: Rapport De Recherche Inria <>
• Submitted on: Wednesday, 24 May 2006 12:39:01
• Updated on: Wednesday, 31 May 2006 14:24:27