1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
\begin{thebibliography}{10}
\bibitem{burnikel:exact:thesis}
C.~Burnikel.
\newblock {\em Exact Computation of {Voronoi} Diagrams and Line Segment
Intersections}.
\newblock Ph.{D} thesis, Universit{\"a}t des Saarlandes, March 1996.
\bibitem{bfms:easy:99}
C.~Burnikel, R.~Fleischer, K.~Mehlhorn, and S.~Schirra.
\newblock Exact geometric computation made easy.
\newblock In {\em Proc. 15th ACM Symp. Comp. Geom.}, pages 341--450, 1999.
\bibitem{mehlhorn-etal:sep-bd:00}
C.~Burnikel, R.~Fleischer, K.~Mehlhorn, and S.~Schirra.
\newblock A strong and easily computable separation bound for arithmetic
expressi ons involving radicals.
\newblock {\em Algorithmica}, 27:87--99, 2000.
\bibitem{bfs:exact-cascaded:01}
C.~Burnikel, S.~Funke, and M.~Seel.
\newblock Exact geometric computation using cascading.
\newblock {\em International J. Comp. Geometry and Applications},
11(3):245--266, 2001.
\newblock Special Issue.
\bibitem{bkmnsu:exact:95}
C.~Burnikel, J.~K{\"o}nnemann, K.~Mehlhorn, S.~N{\"a}her, S.~Schirra, and
C.~Uhrig.
\newblock Exact geometric computation in {LEDA}.
\newblock In {\em Proc. 11th ACM Symp. Computational Geom.}, pages C18--C19,
1995.
\bibitem{fortune-vanwyk:exact}
S.~J. Fortune and C.~J. van Wyk.
\newblock Efficient exact arithmetic for computational geometry.
\newblock In {\em Proc. 9th ACM Symp. on Computational Geom.}, pages 163--172,
1993.
\bibitem{fortune-vanwyk:static:96}
S.~J. Fortune and C.~J. van Wyk.
\newblock Static analysis yields efficient exact integer arithmetic for
computational geometry.
\newblock {\em ACM Transactions on Graphics}, 15(3):223--248, 1996.
\bibitem{klpy:core:98}
V.~Karamcheti, C.~Li, I.~Pechtchanski, and C.~Yap.
\newblock A core library for robust numeric and geometric computation.
\newblock In {\em Proc.~15th ACM Symp.~on Computational Geometry}, pages
351--359, June 1999.
\newblock Miami Beach, Florida.
\bibitem{kln:delaunay:91}
M.~Karasick, D.~Lieber, and L.~R. Nackman.
\newblock Efficient {D}elaunay triangulation using rational arithmetic.
\newblock {\em ACM Trans. on Graphics}, 10:71--91, 1991.
\bibitem{li-pion-yap:progress:04}
C.~Li, S.~Pion, and C.~Yap.
\newblock Recent progress in exact geometric computation.
\newblock {\em Journal of Logic and Algebraic Programming}, 2004.
\newblock To appear. Special issue on ``Practical Development of Exact Real
Number Computation''.
\bibitem{li-yap:constructiveBound:00}
C.~Li and C.~Yap.
\newblock A new constructive root bound for algebraic expressions.
\newblock In {\em Proc.~12th ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages 496--505. ACM and SIAM, Jan. 2001.
\bibitem{orourke:bk}
J.~O'Rourke.
\newblock {\em Computational Geometry in {C}}.
\newblock Cambridge University Press, second edition edition, 1998.
\bibitem{ouchi:thesis}
K.~Ouchi.
\newblock {Real/Expr}: Implementation of an exact computation package.
\newblock Master's thesis, New York University, Department of Computer Science,
Courant Institute, January 1997.
\bibitem{pion-yap:kary:03}
S.~Pion and C.~Yap.
\newblock Constructive root bound method for $k$-ary rational input numbers.
\newblock In {\em 19th ACM Symp. on Comp.Geometry}, pages 256--263, San Diego,
California., 2003.
\bibitem{schirra:robustness-survey:98}
S.~Schirra.
\newblock Robustness and precision issues in geometric computation.
\newblock Report MPI-I-98-1-004, Max-Planck-Institut f{\"u}r Informatik,
Saarbr{\"u}cken, Germany, Jan 1998.
\newblock To appear in {\em Handbook on Computational Geometry}, edited by
J.R.~Sack and J.~Urrutia.
\bibitem{shewchuk:adaptive:96}
J.~R. Shewchuk.
\newblock Robust adaptive floating-point geometric predicates.
\newblock In {\em Proc.~12th ACM Symp.~on Computational Geom.}, pages 141--150.
Association for Computing Machinery, May 1996.
\bibitem{tyl:zero-test:00}
D.~Tulone, C.~Yap, and C.~Li.
\newblock Randomized zero testing of radical expressions and elementary
geometry theorem proving.
\newblock In {\em International Workshop on Automated Deduction in Geometry
(ADG'00), Zurich, Switzerland}, Sept. 2000.
\newblock Preprint: {\tt ftp://cs.nyu.edu/pub/local/yap/exact/}.
\bibitem{yap:brown-cgc:98}
C.~Yap.
\newblock A new number core for robust numerical and geometric libraries.
\newblock In {\em 3rd CGC Workshop on Geometric Computing}, 1998.
\newblock Invited Talk. Brown University, Oct 11--12, 1998. Abstracts, {\tt
http://www.cs.brown.edu/cgc/cgc98/home.html}.
\bibitem{yap:exact}
C.~K. Yap.
\newblock Towards exact geometric computation.
\newblock {\em Computational Geometry: Theory and Applications}, 7:3--23, 1997.
\bibitem{yap:algebra-bk}
C.~K. Yap.
\newblock {\em Fundamental Problems in Algorithmic Algebra}.
\newblock Oxford University Press, 2000.
\newblock A version is available at URL {\tt
ftp:/Preliminary/cs.nyu.edu/pub/local/yap/algebra-bk}.
\bibitem{yap:crc}
C.~K. Yap.
\newblock Robust geometric computation.
\newblock In J.~E. Goodman and J.~O'Rourke, editors, {\em Handbook of Discrete
and Computational Geometry}, chapter~41, pages 927--952. Chapmen \& Hall/CRC,
Boca Raton, FL, 2nd edition, 2004.
\newblock Expanded from 1997 version.
\bibitem{yap-dube:paradigm}
C.~K. Yap and T.~Dub\'e.
\newblock The exact computation paradigm.
\newblock In D.-Z. Du and F.~K. Hwang, editors, {\em Computing in Euclidean
Geometry}, volume~1 of {\em Lecture Notes Series on Computing}, pages
452--492. World Scientific, Singapore, 2nd edition, 1995.
\end{thebibliography}
|
