点と平面との位置関係を判定する高速かつロバストなアルゴリズム(実用,計算の品質,<特集>平成18年研究部会連合発表会)

概要

論文の詳細を見る
This paper is concerned with the computational geometry. A number of geometric problems can be boiled down to the determinant predicates, i.e. whether the sign of the determinant is positive, negative or zero. Among such problems, the ORIENT3D is focused in this paper. A fast and adaptive method for rigorously solving ORIENT3D is proposed. The proposed method in this paper is based on a new accurate floating-point summation algorithm which has just been developed by Rump, Ogita and Oishi. The proposed method ideally works with depending on difficulty of the problem, i.e., if the condition number of the problem becomes larger, then the computational cost for the method gradually increases. Numerical results are presented for illustrating that the proposed method is faster than the state-of-the-art method proposed by Demmel-Hida.
2006-12-25