Evaluating signs of determinants using single-precision arithmeti

Abstract : We propose a method to evaluate signs of 2x2 and 3x3 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 it slows down the computing time by only a small factor with respect to floating-point calculation.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00090613
Contributor : Olivier Devillers <>
Submitted on : Friday, September 1, 2006 - 10:38:07 AM
Last modification on : Wednesday, March 7, 2018 - 10:43:01 AM
Long-term archiving on: Tuesday, April 6, 2010 - 12:43:40 AM

Identifiers

Collections

Citation

Francis Avnaim, Jean-Daniel Boissonnat, Olivier Devillers, Franco Preparata, Mariette Yvinec. Evaluating signs of determinants using single-precision arithmeti. Algorithmica, Springer Verlag, 1997, 17 (2), pp.111-132. ⟨10.1007/BF02522822⟩. ⟨inria-00090613⟩

Share

Metrics

Record views

294

Files downloads

189