Efficient Delaunay triangulation using rational arithmetic

Many fundamental tests performed by geometric algorithms can be formulated in terms of finding the sign of a determinant. When these tests are implemented using fixed-precision arithmetic such as floating point, they can produce incorrect answers; when they are implemented using arbitrary-precision arithmetic, they are expensive to compute. We present adaptive-precision algorithms for finding the signs of determinant of matrices with integer and rational elements. These algorithms were developed and tested by integrating them into the Guibas–Stolfi Delaunay triangulation algorithm. Through a combination of algorithm design and careful engineering of the implementation, the resulting program can triangulate a set of random rational points in the unit circle only four to five times slower than can a floating-point implementation of the algorithm. The algorithms, engineering process, and software tools developed are described