Inner and outer rounding of Boolean operations on lattice polygonal regions

DOI10.1016/J.COMGEO.2004.08.005MaRDI QIDQ2575584zbMATH OpenOpenAlexFDO

Authors Olivier Devillers, Philippe Guigue

Publication date 5 December 2005

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0604059

zbMATH Keywords

geometric roundingintersectionlattice polygonal regionset operations

Mathematics Subject Classification ID

Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Roundoff error (65G50)

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--[Yap et Dube] 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 with integer vertices which respectively is included and contains the true intersection. We also prove interesting results on the Hausdorff distance, the size and the convexity of these polygonal regions.

Review text

New methods for the determination of geometric interval containing the exact result of set operations are presented. The authors explain the problem in form of solving the intersection of two planar lattice polygonal regions (vertices of planar lattice polygonal regions have integer coordinates). Given two intersecting lattice polygonal regions, two new lattice polygonal regions are constructed: inner and outer rounding. The exact result of intersection is contained in the geometric interval. Limits of the geometric interval are created by these two new lattice polygonal regions. To obtain the inner and outer rounding versions, the reflex vertical decomposition of the exact intersection region is used. The presented method guarantees that the biggest distance between the point on the rounded boundary and the point on the exact boundary is less than \(\sqrt{2}\). A generalization of the suggested method to general regions (vertices of general regions do not have to have integer coordinates) and to the other set operations is presented.

Recommendations

• Inner and outer rounding of set operations on lattice polygonal regions
• Polyhedral sets and integer rounding
• Rounding of Polytopes in the Real Number Model of Computation
• Flexible rounding operation for polyhedra
• scientific article; zbMATH DE number 5788338
• On the Voronoi Regions of Certain Lattices
• Boolean algebra over linear polyhedra
• Approximation of boolean functions by combinatorial rectangles

Cites work

• Look — a Lazy Object-Oriented Kernel for geometric computation
• Practical segment intersection with finite precision output
• Rounding Arrangements Dynamically
• Shortest path geometric rounding
• Vertex-rounding a three-dimensional polyhedral subdivision

Cited in

(4)

• A procedure for computing the symmetric difference of regions defined by polygonal curves
• scientific article; zbMATH DE number 1947391 (Why is no real title available?)
• scientific article; zbMATH DE number 852341 (Why is no real title available?)
• Inner and outer rounding of set operations on lattice polygonal regions

Describes a project that uses

Uses Software

• LOOK

This page was built for publication: Inner and outer rounding of Boolean operations on lattice polygonal regions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575584)