幾何アルゴリズム加速のための混合演算に関する研究

概要

論文の詳細を見る
A widely used strategy to decrease the execution time of robust geometric algorithms using multiprecision integer arithmetic is the hybrid use of integer and floating-point arithmetic. In this strategy, multiprecision integer arithmetic is avoided if the sign decision in floating-point arithmetic used in advance is regarded as sufficiently reliable. It is important for this strategy to estimate the upper bound of the error calculated in floating-point arithmetic. However, the method of the estimation is not unique. The more tightly the error is estimated, the more frequently multiprecision integer arithmetic is avoided. However, a tight upper bound requires high computational cost. This paper investigates how the suitable estimation varies as the type and the scale of inputs vary. Experimental consideration is done using the incremental method for constructing the Voronoi diagram as an example of the geometric algorithm.
日本応用数理学会の論文
2004-06-25