Skip to Main content Skip to Navigation
Conference papers

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 - Laboratoire d'informatique GRAphique, VIsion et Robotique de Grenoble, 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Team Evasion Connect in order to contact the contributor
Submitted on : Tuesday, August 17, 2010 - 3:16:57 PM
Last modification on : Monday, December 28, 2020 - 3:44:02 PM


  • HAL Id : inria-00510113, version 1




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. ⟨inria-00510113⟩



Record views