Adaptive and efficient algorithm for 2D orientation problem. (English) Zbl 1185.65037

Summary: This paper is concerned with a robust geometric predicate for the 2D orientation problem. Recently, a fast and accurate floating-point summation algorithm is investigated by S. M. Rump, T. Ogita and S. Oishi [SIAM J. Sci. Comput. 31, No. 1, 189–224 (2008; Zbl 1185.65082)], which provably outputs a result faithfully rounded from the exact value of the summation of floating-point numbers. We optimize their algorithm for applying it to the 2D orientation problem which requires only a correct sign of a determinant of a \(3\times 3\) matrix. Numerical results illustrate that our algorithm works fairly faster than the state-of-the-art algorithm in various cases.


65D18 Numerical aspects of computer graphics, image analysis, and computational geometry


Zbl 1185.65082
Full Text: DOI Euclid


[1] ANSI/IEEE, IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985 edition. IEEE, New York, 1985.
[2] T.J. Dekker, A floating-point technique for extending the available precision. Numer. Math.,18, (1971), 224–242. · Zbl 0226.65034
[3] J. Demmel and Y. Hida, Fast and accurate floating point summation with application to computational geometry. Numerical Algorithms,37 (2004), 101–112. · Zbl 1074.65054
[4] N.J. Higham, Accuracy and Stability of Numerical Algorithms, second edition. SIAM Publications, Philadelphia, 2002. · Zbl 1011.65010
[5] T. Ogita, S. M. Rump and S. Oishi, Accurate sum and dot product. SIAM J. Sci. Comput.,26 (2005), 1955–1988. · Zbl 1084.65041
[6] S.M. Rump, T. Ogita and S. Oishi, Accurate floating-point summation part I: Faithful rounding. SIAM J. Sci. Comput.,31 (2008), 189–224. · Zbl 1185.65082
[7] S.M. Rump, T. Ogita and S. Oishi, Accurate floating-point summation part II: Sign,K-fold faithful and rounding to nearest. SIAM J. Sci. Comput.,31 (2008), 1269–1302. · Zbl 1190.65074
[8] J.R. Shewchuk, Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry,18 (1997), 305–363. · Zbl 0892.68098
[9] J.R. Shewchuk, Delaunay refinement algorithms for triangular mesh generation. Computational Geometry: Theory and Applications,22 (2002), 21–74. · Zbl 1016.68139
[10] MATLAB Programming version 7, the Mathworks.
[11] G.H. Golub and C.F. Van Loan, Matrix Computations, third edition. The Johns Hopkins University Press, 1996. · Zbl 0865.65009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.