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

Ozaki, Katsuhisa; Ogita, Takeshi; Rump, Siegfried M.; Oishi, Shin’ichi

Japan J. Ind. Appl. Math. 26, No. 2-3, 215-231 (2009).

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.

MSC:

65D18

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

Keywords:

robust geometric predicate; 2D orientation problem; floating-point arithmetic; accurate algorithm; numerical results

Citations:

Zbl 1185.65082

Software:

mctoolbox; Matlab; Triangle

References:

[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 · doi:10.1007/BF01397083
[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 · doi:10.1023/B:NUMA.0000049458.99541.38
[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 · doi:10.1137/030601818
[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 · doi:10.1137/050645671
[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 · doi:10.1137/07068816X
[8]	J.R. Shewchuk, Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry,18 (1997), 305–363. · Zbl 0892.68098 · doi:10.1007/PL00009321
[9]	J.R. Shewchuk, Delaunay refinement algorithms for triangular mesh generation. Computational Geometry: Theory and Applications,22 (2002), 21–74. · Zbl 1016.68139 · doi:10.1016/S0925-7721(01)00047-5
[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