Efficient method of adaptive sign detection for 4×4 determinants using a standard arithmetic processing unit

We propose an efficient and exact method for the adaptive sign detection of 4×4 determinants using a standard arithmetic unit. The entities of determinants are variable length integers (integers of arbitrary bit length). The integers are expressed in 16-bit data units, and the sign detection is reduced to the computation of 4×4 determinants of 16-bit integers. To accelerate the computation, the calculation is performed by using a standard arithmetic unit. We have implemented our method and confirmed that it significantly improves the computation time of 4×4 determinants. The method can be applicable to many geometric algorithms that need the exact sign evaluation of 4×4 determinants, especially to construct robust geometric algorithms.