Inner and outer rounding of set operations on lattice polygonal regions

Olivier Devillers 1 Philippe Guigue 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating pointarithmetic are often an obstacle to obtain practical implementation of geometric algorithms. If the adoption of the exact computation paradigm [13] gives a satisfactory solution to this kind of problemsfor purely combinatorial algorithms this solution does not allow to solvein practice the case of algorithms that cascade the construction of new geometric objects.In this paper we consider the problem of rounding the intersection of two polygonal regionsonto the integer lattice with inclusion properties. Namely given two polygonal regions A and B having their vertices on the integer lattice the inner and outer rounding modesconstruct two polygonal regions with integer vertices such that they respectively are included and containing the exact intersection of A and B. We also prove interesting results on the Hausdorff distance the size and the convexity of these polygonal regions.
Type de document :
Communication dans un congrès
Proceedings of the annual symposium on Computational geometry, 2004, Brooklynn, United States. ACM, pp.429-437, 〈10.1145/997817.997881〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01179036
Contributeur : Olivier Devillers <>
Soumis le : mardi 21 juillet 2015 - 14:57:41
Dernière modification le : samedi 27 janvier 2018 - 01:30:47

Identifiants

Collections

Citation

Olivier Devillers, Philippe Guigue. Inner and outer rounding of set operations on lattice polygonal regions. Proceedings of the annual symposium on Computational geometry, 2004, Brooklynn, United States. ACM, pp.429-437, 〈10.1145/997817.997881〉. 〈hal-01179036〉

Partager

Métriques

Consultations de la notice

153