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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00338566
Contributor : Olivier Devillers <>
Submitted on : Thursday, November 13, 2008 - 4:05:25 PM
Last modification on : Wednesday, March 7, 2018 - 10:37:26 AM
Long-term archiving on : Monday, June 7, 2010 - 9:24:07 PM

File

ads-rdppw-00.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

254

Files downloads

149