Removing degeneracies by perturbing the problem or perturbing the world - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Reliable Computing Year : 2000

Removing degeneracies by perturbing the problem or perturbing the world

Pierre Alliez
Olivier Devillers

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.
Fichier principal
Vignette du fichier
ads-rdppw-00.pdf (274.03 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00338566 , version 1 (13-11-2008)

Identifiers

Cite

Pierre Alliez, Olivier Devillers, Jack Snoeyink. Removing degeneracies by perturbing the problem or perturbing the world. Reliable Computing, 2000, ⟨10.1023/A:1009942427413⟩. ⟨inria-00338566⟩
125 View
147 Download

Altmetric

Share

Gmail Facebook X LinkedIn More