• Media type: E-Article
  • Title: Efficient Delaunay triangulation using rational arithmetic
  • Contributor: Karasick, Michael; Lieber, Derek; Nackman, Lee R.
  • Published: Association for Computing Machinery (ACM), 1991
  • Published in: ACM Transactions on Graphics, 10 (1991) 1, Seite 71-91
  • Language: English
  • DOI: 10.1145/99902.99905
  • ISSN: 0730-0301; 1557-7368
  • Keywords: Computer Graphics and Computer-Aided Design
  • Origination:
  • Footnote:
  • Description: 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.
  • Access State: Open Access