Efficient Delaunay triangulation using rational arithmetic
Michael Karasick, Derek Lieber, Lee R. Nackman · ACM Transactions on Graphics · 1991
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 determinants 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.
Cited by 121 works. doi:10.1145/99902.99905 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Proceedings of the 30th IEEE symposium on Foundations of computer science
- An Algorithmic Theory of Numbers, Graphs and Convexity
- Linear Algebra and Matrix Theory
- Writing Efficient Programs
- Verifiable implementations of geometric algorithms using finite precision arithmetic
- Finite-resolution computational geometry
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Epsilon geometry: building robust algorithms from imprecise computations