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
• Publication:4336067
• Reliable and Efficient Computational Geometry Via Controlled Perturbation
• Shortest path geometric rounding
• Publication:3809109

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)

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

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)