Published in

Elsevier, Computational Geometry, 1-2(33), p. 3-17, 2006

DOI: 10.1016/j.comgeo.2004.08.005

Links

Tools

Export citation

Search in Google Scholar

Inner and Outer Rounding of Boolean Operations on Lattice Polygonal Regions

Journal article published in 2006 by Olivier Devillers ORCID, Philippe Guigue
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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 [C.K. Yap, T. Dubé, The exact computation paradigm, in: D.-Z. Du, F.K. Hwang (Eds.), Computing in Euclidean Geometry, in: Lecture Notes Series on Computing, vol. 4, second ed., World Scientific, Singapore, 1995, pp. 452–492, http://cs.nyu.edu/cs/faculty/yap/papers/paradigm.ps] 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 A and B 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.