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

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.