Titre :  Qualitative Symbolic Perturbations

Exposant : Menelaos Karavelas

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

This is joint work with Olivier Devillers and Monique Teillaud