|
 ABSTRACT
We experiment with exact integer arithmetic to implement primitives for geometric algorithms. Naive use of exact arithmetic—either modular or multiprecision integer—increases execution time dramatically over the use of floating-point arithmetic. By combining tuned multiprecision integer arithmetic and a floating-point filter based on interval analysis, we can obtain the effect of exact integer arithmetic at a cost close to that of floating-point arithmetic. We describe an experimental expression compiler that conveniently packages our techniques.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
E. H. Bareiss, Computational solution of matrix problems over an integral domain, j. Inst. Maths Applics 10:68-104, 1972.
|
| |
2
|
J. L. Bentley, B. Kernighan, C. Van Wyk, An elementary C cost model, UNIX Review 9(2):38-48, 1991.
|
| |
3
|
K.L. Clarkson, Safe and effective determinant evaluation, 33th Syrup. on Found. Comp. $ci. 387-395, 1992.
|
| |
4
|
|
 |
5
|
|
| |
6
|
S. J. Fortune, Voronoi diagrams and Delaunay triangulations, Euclidean Geometry and Computers, World Scientific Publishing Co., D.A. Du, F.K. Hwang, eds., 1992.
|
| |
7
|
|
| |
8
|
|
| |
9
|
|
| |
10
|
D. E. Knuth, $eminumerical Algorithms, Volume 2 of The Art of Computer Programming, 2d ed., Addison-Wesley, 1981.
|
| |
11
|
C.L. Lawson, Software for e1 surface interpolation, Mathematical Software III 161-194, J.R. Rice, ed., Academic Press, 1977.
|
| |
12
|
|
| |
13
|
|
| |
14
|
B. Serpette, J. Vuillemin, J.C. Hervd. BigNum: a portable and efficient package k)r arbitraryprecision arithmetic, INRIA.
|
| |
15
|
M. Shamos, D. Hoey, Closest-point problems, Pvoc. 16th Ann. Symp. Found. Comp. Sci. 151-162, 1975.
|
| |
16
|
K. Sugihara, M. Iri, Geometric algorithms in finiteprecision arithmetic, Research Memorandum RMI 88-10, University of Tokyo, September, 1988.
|
| |
17
|
K. Sugihara, M. Iri, Construction of the Voronoi diagram for one million generators in single precision arithmetic, First Canadian Conference on Computational Geometry, Montreal, Canada, 1989.
|
CITED BY 29
|
|
V. Karamcheti , C. Li , I. Pechtchanski , C. Yap, A core library for robust numeric and geometric computation, Proceedings of the fifteenth annual symposium on Computational geometry, p.351-359, June 13-16, 1999, Miami Beach, Florida, United States
|
|
|
Hervé Brönnimann , Ioannis Z. Emiris , Victor Y. Pan , Sylvain Pion, Computing exact geometric predicates using modular arithmetic with single precision, Proceedings of the thirteenth annual symposium on Computational geometry, p.174-182, June 04-06, 1997, Nice, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C. Burnikel , J. Könemann , K. Mehlhorn , S. Näher , S. Schirra , C. Uhrig, Exact geometric computation in LEDA, Proceedings of the eleventh annual symposium on Computational geometry, p.418-419, June 05-07, 1995, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
John Keyser , Tim Culver , Dinesh Manocha , Shankar Krishnan, MAPC: a library for efficient and exact manipulation of algebraic points and curves, Proceedings of the fifteenth annual symposium on Computational geometry, p.360-369, June 13-16, 1999, Miami Beach, Florida, United States
|
|
|
|
|
|
Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
|
|
|
|
|
|
Hervé Brönnimann , Christoph Burnikel , Sylvain Pion, Interval arithmetic yields efficient dynamic filters for computational geometry, Proceedings of the fourteenth annual symposium on Computational geometry, p.165-174, June 07-10, 1998, Minneapolis, Minnesota, United States
|
|
|
|
|
|
|
|
|
Shankar Krishnan , Mark Foskey , Tim Culver , John Keyser , Dinesh Manocha, PRECISE: efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computation, Proceedings of the seventeenth annual symposium on Computational geometry, p.274-283, June 2001, Medford, Massachusetts, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Keyser , Tim Culver , Mark Foskey , Shankar Krishnan , Dinesh Manocha, ESOLID---A System for Exact Boundary Evaluation, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2