Verifiable implementations of geometric algorithms using finite precision arithmetic
The author discusses two methods for handling round-off errors in finite precision implementations of geometric algorithms. The first method, called data normalization, replaces a given geometric structure by another structure, approximating the original one, and belonging to a set of legal inputs. This set of inputs is defined by restricting the set of accepted configurations to those satisfying certain metric and topological constraints. The method is applied to the modeling of planar polygon regions, where the results of the various geometric operations are corrected by a basic operation of ``accomodation which, in turn, uses two primitive operations of ``vertex shifting and ``edge cracking. The second method, called the hidden variable method, replaces the original structure by a simplified structure with parameters in an infinite precision domain. The method is applied to the problem of determining the topological arrangement of lines in the plane. The new structure replaces a bundle of lines sitting close to each other by a curve satisfying a property of ``approximate monotonicity and approximating a straight line; the number of intersection points and their order relations are kept unchanged. Both methods are shown to provide provably correct finite precision implementations on their legal inputs. The author discusses the various advantages and disadvantages of his two methods; he also provides pseudocode descriptions of their algorithmic implementations.
- Compaction and separation algorithms for non-convex polygons and their applications
- Delaunay triangulations in three dimensions with finite precision arithmetic
- Constructing strongly convex hulls using exact or rounded arithmetic
- A perturbation scheme for spherical arrangements with application to molecular modeling
- Robust gift wrapping for the three-dimensional convex hull
- Recent progress in exact geometric computation
- Robust algorithms for constructing strongly convex hulls in parallel.
- Three-dimensional convex hull as a fruitful source of diagrams
- Constructing strongly convex approximate hulls with inaccurate primitives
- Structural filtering: a paradigm for efficient and exact geometric programs
- A robust algorithm for bisecting a triconnected graph with two resource sets
- An exact general remeshing scheme applied to physically conservative voxelization
- Of What Use Is Floating-Point Arithmetic in Computational Geometry?
- CONTROLLED PERTURBATION FOR ARRANGEMENTS OF CIRCLES
- Inner and outer rounding of set operations on lattice polygonal regions
- Weak Rational Computing for Digital Geometry
- Controlled Perturbation for Certified Geometric Computing with Fixed-Precision Arithmetic
- A Provably Robust Algorithm for Triangle-triangle Intersections in Floating-point Arithmetic
- Robustness issues in geometric algorithms
- Implementing geometric algorithms robustly
- Why is the 3D Delaunay triangulation difficult to construct?
- Evaluating signs of determinants using single-precision arithmetic
- Two design principles of geometric algorithms in finite-precision arithmetic
- An intersection-sensitive algorithm for snap rounding
- Applied computational geometry: Towards robust solutions of basic problems
- Polygon nesting and robustness
This page was built for publication: Verifiable implementations of geometric algorithms using finite precision arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116270)
