Inner and outer rounding of Boolean operations on lattice polygonal regions

DOI10.1016/J.COMGEO.2004.08.005zbMATH Open1090.65023arXivcs/0604059OpenAlexW2196640915MaRDI QIDQ2575584FDOQ2575584

Authors: Olivier Devillers, Philippe Guigue 

Publication date: 5 December 2005

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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
• On the Voronoi Regions of Certain Lattices
• Boolean algebra over linear polyhedra
• Approximation of boolean functions by combinatorial rectangles

zbMATH Keywords

intersectionset operationslattice polygonal regiongeometric rounding

Mathematics Subject Classification ID

Roundoff error (65G50) 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)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)