Efficient Delaunay triangulation using rational arithmetic

ABSTRACT

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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Jon Louis Bentley, Writing Efficient Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 3: M. W. Bern , H. J. Karloff , P. Raghavan , B. Schieber, Fast geometric approximation techniques and geometric embedding problems, Proceedings of the fifth annual symposium on Computational geometry, p.292-301, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73866]
• 4: D. P. Dobkin , D. Silver, Recipes for geometry and numerical analysis - Part I: an empirical study, Proceedings of the fourth annual symposium on Computational geometry, p.93-105, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73404]
• 5: H. Edelsbrunner , E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Proceedings of the fourth annual symposium on Computational geometry, p.118-133, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73406]
• 6: Rida T. Farouki, Numerical Stability in Geometric Algorithms and Representations, Proceedings of the 3rd IMA Conference on the Mathematics of Surfaces, p.83-113, September 19-21, 1988
• 7: FORREST, A. R. Computational geometry and software engineering. Towards a geometric computing environment. In Techniques for Computer Graphics, R. A. Earnshaw and D. F. Rogers, Eds. Springer Verlag, New York, 1987, 23-37.
• 8: FORTUNE, S.J. Stable maintenance of point-set triangulations in two dimensions. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (Oct. 1989). IEEE, New York, 1989.
• 9: GREENE, D. H., AND YAo, F. F, Finite-resolution computational geometry. In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science (1986). IEEE, New York, 1986, 143-152.
• 10: D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73857]
• 11: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 12: C. M. Hoffmann , J. E. Hopcroft , M. S. Karasick, Towards implementing robust geometric computations, Proceedings of the fourth annual symposium on Computational geometry, p.106-117, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73405]
• 13: Christoph M. Hoffmann, The Problems of Accuracy and Robustness in Geometric Computation, Computer, v.22 n.3, p.31-40, March 1989 [doi>10.1109/2.16223]
• 14: M. S. Karasick, On the representation and manipulation of rigid solids, McGill University, Montreal, Que., Canada, 1989
• 15: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 16: LovAsz, L. An Algorithmic Theory o{ Numbers, Graphs and Convexity. Vol. 50. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, 1986.
• 17: Victor J. Milenkovic, Verifiable implementation of geometric algorithms using finite precision arithmetic, Artificial Intelligence, v.37 n.1-3, p.377-401, Dec. 1988 [doi>10.1016/0004-3702(88)90061-6]
• 18: V. Milenkovic, Calculating approximate curve arrangements using rounded arithmetic, Proceedings of the fifth annual symposium on Computational geometry, p.197-207, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73856]
• 19: MUDUR, S. P., AND KOPARKAR, P.A. Interval methods for processing geometric objects. IEEE Comput. Graph. Appl. 4, 2 (Feb. 1984), 7-17.
• 20: NERINC, E.D. Linear Algebra and Matrix Theory. John Wiley, New York, 1970.
• 21: T. Ottmann , G. Theimt , C. Ullrich, Numerical stability of geometric algorithms, Proceedings of the third annual symposium on Computational geometry, p.119-125, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41970]
• 22: PREPARATA, F. P., AND VUILLEMIN, J.E. Practical cellular dividers. INRIA Tech. Pep. 807, Rocquencourt, France, March 1988.
• 23: Segal Segal , Carlo H. Sequin, Partitioning Polyhedral Objects into Nonintersecting Parts, IEEE Computer Graphics and Applications, v.8 n.1, p.53-67, January 1988 [doi>10.1109/38.490]
• 24: Bjarne Stroustrup, The C++ programming language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 25: STROUSTRUP, B. Parameterized types for C*+. In Proceedings of the USENIX C*+ Con{erence (Oct. 1988). USENIX Association.
• 26: K. Sugihara, On finite-precision representations of geometric objects, Journal of Computer and System Sciences, v.39 n.2, p.236-247, Oct. 1989 [doi>10.1016/0022-0000(89)90046-9]
• 27: SUGIHARA, g., AND IRl, M. Construction of the Voronoi diagram for one million generators in single-precision arithmetic. Paper presented at the First Canadian Conference on Computational Geometry. Montreal, Aug. 1989.
• 28: C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation, Languages, Performance, Reliability