Interval arithmetic yields efficient dynamic filters for computational geometry

DOI10.1016/S0166-218X(00)00231-6zbMath0967.68157OpenAlexW2080666584MaRDI QIDQ5929320

Christoph Burnikel, Sylvain Pion, Hervé Brönnimann

Publication date: 4 April 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00231-6

zbMATH Keywords

floating-point filters

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (20)

Faster geometric algorithms via dynamic determinant computation ⋮ Simple floating-point filters for the two-dimensional orientation problem ⋮ An adaptable and extensible geometry kernel ⋮ Advanced programming techniques applied to CGAL's arrangement package ⋮ Efficient Predicate Evaluation Using Randomized Degeneracy Detection ⋮ Far-field reflector problem and intersection of paraboloids ⋮ ON DELETION IN DELAUNAY TRIANGULATIONS ⋮ A HYBRID APPROACH FOR DETERMINANT SIGNS OF MODERATE-SIZED MATRICES ⋮ CONTROLLED PERTURBATION FOR ARRANGEMENTS OF CIRCLES ⋮ Meshing skin surfaces with certified topology ⋮ Fast floating-point filters for robust predicates ⋮ A robust algorithm for geometric predicate by error-free determinant transformation ⋮ Recent progress in exact geometric computation ⋮ Formally certified floating-point filters for homogeneous geometric predicates ⋮ Foundations of Exact Rounding ⋮ \texttt{ColDICE}: A parallel Vlasov-Poisson solver using moving adaptive simplicial tessellation ⋮ Verified bounds for the determinant of real or complex point or interval matrices ⋮ Of What Use Is Floating-Point Arithmetic in Computational Geometry? ⋮ LOOK: A lazy object-oriented kernel design for geometric computation ⋮ The design of the Boost interval arithmetic library

Uses Software

• Hull
• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Evaluating signs of determinants using single-precision arithmetic
• Derived eigenvalues of symmetric matrices, with applications to distance geometry
• A sweepline algorithm for Voronoi diagrams
• Sign determination in residue number systems
• A probabilistic analysis of the power of arithmetic filters
• Adaptive precision floating-point arithmetic and fast robust geometric predicates
• Foundation of a computable solid modelling.

This page was built for publication: Interval arithmetic yields efficient dynamic filters for computational geometry