Dealing with degeneracies and numerical imprecisions when computing visibility graphs

Stéphane Rivière 1
1 iMAGIS - Models, Algorithms and Geometry for Computer Generated Image Graphics
GRAVIR - IMAG - Graphisme, Vision et Robotique, Inria Grenoble - Rhône-Alpes
Abstract : Most algorithms in computational geometry assume that the input is in ”general position”, that is that no degenerate cases occur (such as three aligned points , or three convergent lines . . . ). But in practice, when the size of the input becomes significant, degenerate configurations occur and programs fail. Things get worse when the program must face imprecise computations. Some general tools have been developed to cope with these problems. For solving degeneracies symbolic perturbation schemes are employed (e.g. [EM90], [Yap90]) : coordinates of input are symbolically perturbed so that degeneracies are removed. Other techniques such as the epsilon geometry ([GSS89]) do the actual geometric computations but consider that the results have an imprecision up to ε and decisions made on these results take this imprecision into account. Finally techniques are developed to do exact computations (e.g. [FV93]) and avoid imprecision problems. These general techniques can be used as ”black boxes” for geometric computation in algorithms. This has the advantage that it can be applied to a large range of algorithms, but these black boxes have in general an extra cost which can reduce the performance of the program. We consider here two algorithms for computing visibility graphs and study how to apply the idea of symbolic perturbation, not for black boxes creation, but for direct modifications of the algorithm, making it robust.
Type de document :
Communication dans un congrès
Proceedings of European Workshop on Computational Geometry (CG'96), 1996, Münster, Germany. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00510113
Contributeur : Team Evasion <>
Soumis le : mardi 17 août 2010 - 15:16:57
Dernière modification le : mercredi 11 avril 2018 - 01:55:02

Identifiants

  • HAL Id : inria-00510113, version 1

Collections

INRIA | UGA | IMAG

Citation

Stéphane Rivière. Dealing with degeneracies and numerical imprecisions when computing visibility graphs. Proceedings of European Workshop on Computational Geometry (CG'96), 1996, Münster, Germany. 1996. 〈inria-00510113〉

Partager

Métriques

Consultations de la notice

83