Fast evaluation of the sign of determinants

We propose a method to evaluate signs of $2\times 2$ and $3\times 3$ determinants with $b$-bit integer entries using only $b$ 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 experimental results show that our method compares favorably to other exact computation methods. (Coauthored with F. Avnaim, O. Devillers, F.~Preparata, M. Yvinec.)