HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions

Olivier Devillers 1 Philippe Guigue
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 point arithmetic are often an obstacle to obtain practical implementation of geometric algorithms. If the adoption of the exact computation paradigm gives a satisfactory solution to this kind of problems for purely combinatorial algorithms, this solution does not allow to solve in practice the case of algorithms that cascade the construction of new geometric objects. In this report, we consider the problem of rounding the intersection of two polygonal regions onto the integer lattice with inclusion properties. Namely, given two polygonal regions and having their vertices on the integer lattice, the inner and outer rounding modes construct two polygonal regions and with integer vertices such that . We also prove interesting results on the Hausdorff distance, the size and the convexity of these polygonal regions.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:48:41 PM
Last modification on : Friday, February 4, 2022 - 3:16:11 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:31:14 PM


  • HAL Id : inria-00071513, version 1



Olivier Devillers, Philippe Guigue. Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions. RR-5070, INRIA. 2003. ⟨inria-00071513⟩



Record views


Files downloads