Verifiable implementations of geometric algorithms using finite precision arithmetic

DOI10.1016/0004-3702(88)90061-6MaRDI QIDQ1116270zbMATH OpenOpenAlexFDO

Authors Victor J. Milenkovic

Publication date 1988

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(88)90061-6

zbMATH Keywords

round-off errorsgeometric algorithmsfinite precisionalgorithmic implementationsdata normalizationedge crackinggeometric operationshidden variable methodplanar polygon regionstopological arrangement of lines in the plane

Mathematics Subject Classification ID

Roundoff error (65G50) Artificial intelligence (68T99) Algorithms for approximation of functions (65D15) Software, source code, etc. for problems pertaining to geometry (51-04)

Recommendations

• Two design principles of geometric algorithms in finite-precision arithmetic
• scientific article; zbMATH DE number 1008329
• Reliable and Efficient Computational Geometry Via Controlled Perturbation
• Shortest path geometric rounding
• scientific article; zbMATH DE number 4078610

Cites work

• Constructing Arrangements of Lines and Hyperplanes with Applications
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Topologically sweeping an arrangement

Cited in

(26)

• A Provably Robust Algorithm for Triangle-triangle Intersections in Floating-point Arithmetic
• Structural filtering: a paradigm for efficient and exact geometric programs
• Applied computational geometry: Towards robust solutions of basic problems
• Constructing strongly convex hulls using exact or rounded arithmetic
• Inner and outer rounding of set operations on lattice polygonal regions
• Polygon nesting and robustness
• Two design principles of geometric algorithms in finite-precision arithmetic
• Delaunay triangulations in three dimensions with finite precision arithmetic
• Weak Rational Computing for Digital Geometry
• Why is the 3D Delaunay triangulation difficult to construct?
• Evaluating signs of determinants using single-precision arithmetic
• An exact general remeshing scheme applied to physically conservative voxelization
• Three-dimensional convex hull as a fruitful source of diagrams
• An intersection-sensitive algorithm for snap rounding
• Constructing strongly convex approximate hulls with inaccurate primitives
• Compaction and separation algorithms for non-convex polygons and their applications
• Of What Use Is Floating-Point Arithmetic in Computational Geometry?
• A robust algorithm for bisecting a triconnected graph with two resource sets
• A perturbation scheme for spherical arrangements with application to molecular modeling
• Robust algorithms for constructing strongly convex hulls in parallel.
• Recent progress in exact geometric computation
• Robust gift wrapping for the three-dimensional convex hull
• Controlled Perturbation for Certified Geometric Computing with Fixed-Precision Arithmetic
• Implementing geometric algorithms robustly
• Robustness issues in geometric algorithms
• CONTROLLED PERTURBATION FOR ARRANGEMENTS OF CIRCLES

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)