A robust algorithm for geometric predicate by error-free determinant transformation

DOI10.1016/J.IC.2011.09.007MaRDI QIDQ714616zbMATH OpenOpenAlexFDO

Authors Katsuhisa Ozaki, Takeshi Ogita, Shin'ichi Oishi

Publication date 11 October 2012

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2011.09.007

zbMATH Keywords

algorithmcomputational geometrynumerical experimentserror-free determinant transformationverified numerical computation

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Algorithms with automatic result verification (65G20)

Recommendations

• Adaptive and efficient algorithm for 2D orientation problem
• Adaptive precision floating-point arithmetic and fast robust geometric predicates
• Simple floating-point filters for the two-dimensional orientation problem
• Fast and accurate floating point summation with application to computational geometry
• Formally certified floating-point filters for homogeneous geometric predicates

Cites work

• scientific article; zbMATH DE number 1256676 (Why is no real title available?)
• Accuracy and Stability of Numerical Algorithms
• Accurate Floating-Point Summation Part I: Faithful Rounding
• Accurate Sum and Dot Product
• Accurate floating-point summation. II: Sign, \(K\)-fold faithful and rounding to nearest
• Adaptive and efficient algorithm for 2D orientation problem
• Adaptive precision floating-point arithmetic and fast robust geometric predicates
• Certification of numerical computation of the sign of the determinant of a matrix
• Classroom examples of robustness problems in geometric computations
• Delaunay refinement algorithms for triangular mesh generation
• Efficient exact evaluation of signs of determinants
• Evaluating signs of determinants using single-precision arithmetic
• Formally certified floating-point filters for homogeneous geometric predicates
• Interval arithmetic yields efficient dynamic filters for computational geometry
• Recent progress in exact geometric computation
• The computational geometry algorithms library CGAL

Cited in

(1)

• Adaptive and efficient algorithm for 2D orientation problem

Describes a project that uses

Uses Software

• Matlab
• mctoolbox
• Triangle
• Hull

This page was built for publication: A robust algorithm for geometric predicate by error-free determinant transformation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714616)