Qualitative Symbolic Perturbation: a new geometry-based perturbation framework

Abstract : In the literature, the generic way to address degeneracies in computational geometry is the Symbolic Perturbation paradigm: the input is made dependent of some parameter ε so that for ε positive and close to zero, the input is close to the original input, while at the same time, in non-degenerate position. A geometric predicate can usually be seen as the sign of some function of the input. In the symbolic perturbation paradigm, if the function evaluates to zero, the input is perturbed by a small positive ε, and the sign of the function evaluated at the perturbed input is used instead. The usual way of using this approach is what we will call Algebraic Symbolic Perturbation frame- work. When the function to be evaluated is a polynomial of the input, its perturbed version is seen as a polynomial in ε, whose coefficients are polynomials in the input. These coefficients are evaluated by increasing degree in ε until a non-vanishing coefficient is found. The number of these coefficients can be quite large and expressing them in an easily and efficiently computable manner (e.g., factorized) may require quite some work. We propose to address the handling of geometric degeneracies in a different way, namely by means of what we call the Qualitative Symbolic Perturbation framework. We no longer use a single perturbation that must remove all degeneracies, but rather a sequence of perturbations, such that the next perturbation is being used only if the previous ones have not removed the degeneracies. The new perturbation is considered as symbolically smaller than the previous ones. This approach allows us to use simple elementary perturbations whose effect can be analyzed and evaluated: (1) by geometric reasoning instead of algebraic development of the predicate polynomial in ε, and (2) independently of a specific algebraic formulation of the predicate. We apply our framework to predicates used in the computation of Apollonius diagrams in 2D and 3D, as well as the computation of trapezoidal maps of circular arcs.
Document type :
Reports
[Research Report] RR-8153, INRIA. 2012


https://hal.inria.fr/hal-00758631
Contributor : Olivier Devillers <>
Submitted on : Wednesday, December 5, 2012 - 5:08:40 PM
Last modification on : Tuesday, January 6, 2015 - 5:02:03 PM

File

RR-8153.pdf
fileSource_public_author

Identifiers

  • HAL Id : hal-00758631, version 3

Collections

Citation

Olivier Devillers, Menelaos Karavelas, Monique Teillaud. Qualitative Symbolic Perturbation: a new geometry-based perturbation framework. [Research Report] RR-8153, INRIA. 2012. <hal-00758631v3>

Export

Share

Metrics

Consultation de
la notice

218

Téléchargement du document

56