Hypergeometric functions in exact geometric computation. (English) Zbl 1261.68127
Brattka, Vasco (ed.) et al., CCA 2002: computability and complexity in analysis. Papers from the 5th workshop, University of Málaga, Málaga, Spain, July 12–13, 2002. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 66, No. 1, 53-64 (2002).
Summary: Most problems in computational geometry are algebraic. A general approach to address nonrobustness in such problems is exact geometric computation (EGC). There are now general libraries that support EGC for the general programmer (e.g., Core Library, LEDA Real). Many applications require non-algebraic functions as well. In this paper, we describe how to provide non-algebraic functions in the context of other EGC capabilities. We implemented a multiprecision hypergeometric series package which can be used to evaluate common elementary math functions to an arbitrary precision. This can be achieved relatively easily using the Core Library which supports a guaranteed precision level of accuracy. We address several issues of efficiency in such a hypergeometric package: automatic error analysis, argument reduction, preprocessing of hypergeometric parameters, and precomputed constants. Some preliminary experimental results are reported.
For the entire collection see [Zbl 1109.03301].
For the entire collection see [Zbl 1109.03301].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
exact geometric computationReferences:
| [1] | Boissonnat, J.-D.; Yvinec, M., Algorithmic Geometry (1997), Cambridge University Press, Translated by Hervé Brönnimann. |
| [2] | Brönnimann, H.; Burnikel, C.; Pion, S., Interval arithmetic yields efficient dynamic filters for Computation Geometry, ACM Symp. on Computational Geometry, 14, 165-174 (1998) |
| [3] | C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra. Exact geometric computation made easy. In Proc. 15th ACM Symp. Comp. Geom; C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra. Exact geometric computation made easy. In Proc. 15th ACM Symp. Comp. Geom |
| [4] | Burnikel, C.; Fleischer, R.; Mehlhorn, K.; Schirra, S., A strong and easily computable separation bound for arithmetic expressi ons involving radicals, Algorithmica, 27, 87-99 (2000) · Zbl 0953.68136 |
| [5] | C. Burnikel, S. Funke, K. Mehlhorn, and S. Schirra. A separation bound for real algebraic expressions, 2001. preprint (submitted to journal).; C. Burnikel, S. Funke, K. Mehlhorn, and S. Schirra. A separation bound for real algebraic expressions, 2001. preprint (submitted to journal). · Zbl 1006.68960 |
| [6] | Burnikel, C.; Funke, S.; Seel, M., Exact geometric comptuation using cascading, Int’l. J. Computational Geometry and Applications, 11, 3, 245-266 (2001), Special Issue · Zbl 1074.65509 |
| [7] | de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Computational Geometry: Algorithms and Applications (1997), Springer-Verlag: Springer-Verlag Berlin · Zbl 0877.68001 |
| [8] | A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schoenherr. The CGAL kernel: a basis for geometric computation. In M. C. Lin and D. Manocha, editors, Applied Computational Geometry: Towards Geometric Engineering; A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schoenherr. The CGAL kernel: a basis for geometric computation. In M. C. Lin and D. Manocha, editors, Applied Computational Geometry: Towards Geometric Engineering |
| [9] | E. Jeandel. Évaluation rapide de fonctions hypergéométriques. Rapport Technique 242, INRIA, 2000. 17 pages.; E. Jeandel. Évaluation rapide de fonctions hypergéométriques. Rapport Technique 242, INRIA, 2000. 17 pages. |
| [10] | Karamcheti, V.; Li, C.; Pechtchanski, I.; Yap, C., A Core library for robust numerical and geometric libraries, 15th ACM Symp. Computational Geometry, 351-359 (1999) |
| [11] | C. Li and C. Yap. A new constructive root bound for algebraic expressions. In Proc. 12th ACM-SIAM Symposium on Discrete Algorithms; C. Li and C. Yap. A new constructive root bound for algebraic expressions. In Proc. 12th ACM-SIAM Symposium on Discrete Algorithms · Zbl 0988.65037 |
| [12] | C. Li and C. Yap. Recent progress in exact geometric computation. In S. Basu and L. Gonzalez-Vega, editors, Proc. DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, March 12 - 16, 2001http://cs.nyu.edu/exact/doc/; C. Li and C. Yap. Recent progress in exact geometric computation. In S. Basu and L. Gonzalez-Vega, editors, Proc. DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, March 12 - 16, 2001http://cs.nyu.edu/exact/doc/ · Zbl 1080.68106 |
| [13] | Liotta, G.; Preparata, F.; Tamassia, R., Robust proximity queries: an illustration of degree-driven algorithm design, SIAM J. Computing (2001), to apear |
| [14] | Matiyasevich, Y. V., Hilbert’s Tenth Problem (1994), The MIT Press: The MIT Press Cambridge, Massachusetts |
| [15] | Mehlhorn, K.; Näher, S., LEDA: a platform for combinatorial and geometric computing, CACM, 38, 96-102 (1995) |
| [16] | Muller, J.-M., Elementary Functions: Algorithms and Implementation (1997), Birkhäuser: Birkhäuser Boston · Zbl 0892.65005 |
| [17] | Overmars, M., Designing the computational geometry algorithms library CGAL, (Lin, M. C.; Manocha, D., Applied Computational Geometry: Towards Geometric Engineering (1996), Springer: Springer Berlin), 53-58, Lecture Notes in Computer Science No. 1148; Proc. 1st ACM Workshop on Applied Computational Geometry (WACG). · Zbl 1541.68408 |
| [18] | S. Schirra. Precision and robustness in geometric computations. In M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, editors, Algorithmic Foundations of Geographic Information SystemsLecture Notes Comp. Science; S. Schirra. Precision and robustness in geometric computations. In M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, editors, Algorithmic Foundations of Geographic Information SystemsLecture Notes Comp. Science |
| [19] | Weihrauch, K., Computable Analysis (2000), Springer: Springer Berlin · Zbl 0956.68056 |
| [20] | Yap, C., A new number core for robust numerical and geometric libraries, (3rd CGC Workshop on Geometric Computing 1998. Invited Talk (Oct 11-12, 1998), Brown University), For abstracts, see http://www.cs.brown.edu/cgc/cgc98/home.html. |
| [21] | Yap, C. K., Robust geometric computation, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry, chapter 35 (1997), CRC Press LLC: CRC Press LLC Boca Raton, FL), 653-668 · Zbl 0907.68091 |
| [22] | C. K. Yap. Towards exact geometric computation. Computational Geometry: Theory and Applications7; C. K. Yap. Towards exact geometric computation. Computational Geometry: Theory and Applications7 · Zbl 0869.68104 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
