Structural filtering: a paradigm for efficient and exact geometric programs

DOI10.1016/j.comgeo.2004.12.007zbMath1078.65015OpenAlexW2110837821MaRDI QIDQ2486081

Kurt Mehlhorn, Stefan Funke, Stefan Näher

Publication date: 5 August 2005

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

Full work available at URL: https://doi.org/10.1016/j.comgeo.2004.12.007

zbMATH Keywords

algorithmssortingcomputational geometrysearchingexact geometric computationpredicate filteringstructural filtering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Practical distribution-sensitive point location in triangulations, Energy efficient sorting, selection and searching, On design and implementation of a generic number type for real algebraic number computations based on expression dags, Recent progress in exact geometric computation, Longest increasing subsequence under persistent comparison errors, The solution space of sorting with recurring comparison faults, In Praise of Numerical Computation, LOOK: A lazy object-oriented kernel design for geometric computation

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Verifiable implementations of geometric algorithms using finite precision arithmetic
• A probabilistic analysis of the power of arithmetic filters
• The computational geometry algorithms library CGAL
• Walking in a triangulation