Dealing with degeneracies and numerical imprecisions when computing visibility graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1996

Dealing with degeneracies and numerical imprecisions when computing visibility graphs

Résumé

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.
Fichier non déposé

Dates et versions

inria-00510113 , version 1 (17-08-2010)

Identifiants

  • HAL Id : inria-00510113 , version 1

Citer

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⟩
70 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More