Recipes for geometry and numerical analysis - Part I: an empirical study

ABSTRACT

Geometric computations, like all numerical procedures, are extremely prone to roundoff error. However, virtually none of the numerical analysis literature directly applies to geometric calculations. Even for line intersection, the most basic geometric operation, there is no robust and efficient algorithm. Compounding the difficulties, many geometric algorithms perform iterations of calculations reusing previously computed data. In this paper, we explore some of the main issues in geometric computations and the methods that have been proposed to handle roundoff errors. In particular, we focus on one method and apply it to a general iterative intersection problem. Our initial results seem promising and will hopefully lead to robust solutions for more complex problems of computational geometry.

REFERENCES

• 1: Demm86a. Demmel, J., "On Error Analysis in Arithmetic With Varying Relative Precision," TR 251, NYU Dept. of Computer Science, October 1986.
• 2: Faye85a. Faye, J-P. and J. Vignes, "Stochastic Approach Of The Permutation-Perturbation Method For Round-Off Error Analysis," Applied Numerical Mathematics 1, pp. 349-362, 1985.
• 3: Forr85a. Forrest, A. R., "Computational Geometry in Practice," in Fundamental Algorithms for Computer Graphics, ed. R. A. Earnshaw, Springer-Verlag, 1985.
• 4: Forr87a. Forrest, A. R., "'Geometric Computing Environments: Computational Geometry Meets Software Engineering.," Proceedings of the NATO Advanced Study Institute on TFCG & CAD, p. II Cioceo, italy, July 1987.
• 5: Gree86a. Greene, D. and F. Yao, "Finite Resolution Computational Geometry," 27th Annual FOCS Conference Proceedings, pp. 143- 152, Oct. 1986.
• 6: Hoff87a. Hoffmann, C., J. Hopcroft, and M. Karasick, "Robust Set Operation on Polyhedral Solids," Unpublished Manuscript, 1987.
• 7: Knot87& Knott, G. and E. Jou, "A Program to Determine Whether Two Line Segments Intersect," Technical Report CAR-TR-306, CS-TR- 1884,DCR-86-05557, Computer Science Dept. University of Maryland at College Park, August 1987.
• 8: Kom83a. Kornerup, P. and D. Matula, "Finite Precision Rational Arithmetic: An Arithmetic Unit," IEEE Transaction on Computers, vol. c-32, no. 4, April 1983.
• 9: Ulrich W. Kulisch , Willard L. Miranker, Computer Arithmetic in Theory and Practice, Academic Press, Inc., Orlando, FL, 1981
• 10: Madu84a. Madur, S. and P. Koparkar, "Interval Methods for Processing Geometric Objects," IEEE Computer Graphics and Application, pp. 7-17, February 1984.
• 11: Mai179a. Maille, M., "Methodes d'evaluation de la precision d'une mesure ou d'un calcul numerique.," Rapport LJ.T.P., Universite P. et M. Curie, Pads, France, 1979.
• 12: Mair87a. Mairson, H. and J. Stolti, "Reporting and Counting Intersections Between Two Sets of Line Segments," Proceedings of NATO ASI on TFCG & CAD, July 1987.
• 13: Mara73a. Marasa, J. and D. Matula, "A Simulative Study of Correlated Error Propagation in Various Finite-Precision Arithmetics," IEEE Transactions on Computers, vol. c- 22, no. 6, pp. 587-597, June 1973.
• 14: Mile86a. Milenkovic, V., "Verifiable Implementations of Geometric Algorithms Using Finite Precision Arithmetic," Unpublished Manuscript, 1986.
• 15: Mill80a. Miller, Webb and Celia Wrathall, Software For Roundoff Analysis of Matrix Algorithms, Academic Press, NYC, 1980.
• 16: Moor66a. Moore, R. E., Interval Analysis, Prentice Hall, Engelwood Cliffs, NJ, 1966.
• 17: 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]
• 18: Rams82a. Ramshaw, Lyle, "The Braiding of Floating Point Lines," CSL Notebook Entry, Xerox PARC, October 1982.
• 19: Mark Segal , Carlo H. Séquin, Consistent calculations for solids modeling, Proceedings of the first annual symposium on Computational geometry, p.29-38, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323238]
• 20: Deborah E. Silver, Geometry, graphics, and numerical analysis, 1988
• 21: Vand78a. Vandergraft, J., Introduction to Numerical Computations, Academic Press, New York, 1978.
• 22: Vign78a. Vignes, J., "New Methods For Evaluating The Validity Of The Results Of Mathematical Computations," Mathematics and Computers in Simulation XX, pp. 227-249, 1978.
• 23: Vign74a. Vignes, J. and M. La Porte, "Error Analysis In Computing," Proceedings IFIP Congress, pp. 610-614, Stockholm, 1974.
• 24: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis
      G.1.3 Numerical Linear Algebra
          Subjects: Error analysis

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Performance, Reliability, Theory