|
|||||
|
|
Evaluating signs of determinants using single-precision arithmetic |
|
| Authors: | F. Avnaim J. -D. Boissonnat O. Devillers F. P. Preparata M. Yvinec |
| Affiliation: | (1) INRIA, BP93, 06902 Sophia-Antipolis cedex, France;(2) Department of Computer Science, Brown University, 02912-1910 Providence, RI, USA;(3) Laboratoire 13S, INRIA and CNRS, URA 1376, 250 Rue Albert Einstein, 06560 Valbonne, France |
| Abstract: | We propose a method of evaluating signs of 2×2 and 3×3 determinants withb-bit integer entries using onlyb and (b+1)-bit arithmetic, respectively. This algorithm has numerous applications in geometric computation and provides a general and practical approach to robustness. The algorithm has been implemented and compared with other exact computation methods. This work was partially supported by the ESPRIT Basic Research Action 7141 (AL-COMII) and by NSF Grant CCR 91-96176. Part of this work was done while J.-D. Boissonnat was visiting Brown University. |
| Keywords: | Computational geometry Exact arithmetic Precision Robust algorithms |
| 本文献已被 SpringerLink 等数据库收录！ | |