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 geometryerror-free determinant transformationnumerical experimentsverified numerical computation

Mathematics Subject Classification ID

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

Review text

An accurate and robust algorithm for a two-dimensional (2D) orientation problem is proposed. The algorithm is based on the recently developed algorithm on accurate floating-point summation [\textit{S. M. Rump, T. Ogita} and \textit{S. Oishi}, SIAM J. Sci. Comput. 31, No. 1, 189--224 (2008; Zbl 1185.65082)], by which an error-free determinant transformation is possible. Numerical experiments are done to compare the performance of the proposed algorithm with other preceding algorithms in terms of runtime versus condition number.

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

• Accuracy and Stability of Numerical Algorithms
• Accurate Floating-Point Summation Part I: Faithful Rounding
• Accurate floating-point summation. II: Sign, K-fold faithful and rounding to nearest
• Accurate Sum and Dot Product
• 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
• scientific article; zbMATH DE number 1256676 (Why is no real title available?)
• 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
• Hull
• mctoolbox
• Triangle

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)