Exact Geometric Computation

PAPERS


Absolute Approximation of the General Hypergeometric Function
Zilin Du and Chee Yap
(Mar 2005)
Complexity of Robust Approximate Zeros
Vikram Sharma, Zilin Du and Chee Yap
To appear, 13th European Symp. on Algorithms (ESA 2005).
New Upper Bounds For Root Isolation Via Sturm Sequences
Zilin Du and Sharma and Chee Yap
To appear, Workshop on Symbolic and Numeric Computing (SNC), Xian, China, Jul 19--21, 2005.
Shortest Path amidst Disc Obstacles is Computable
E. Chang, S.W. Choi, D. Kwon, H. Park, C. Yap
Proc. ACM Symp. on Computational Geometry July (2005). To appear.
Classroom Examples of Robustness Problems in Geometric Computation
L.Kettner, K.Mehlhorn, S.Pion, S.Schirra, C. Yap
Proc. European Symposium on Algorithms (ESA) Nov 2004.
On Guaranteed Accuracy Computation
C. Yap
Chapter 12 in: ``Geometric Computation'' (Eds. Falai Chen and Dongming Wang) World Scientific Pub.Co., pp.322-373, 2004.
Constructive Root Bound Method for k-Ary Rational Input Numbers
S. Pion and C. Yap
Proc. 19th ACM Symp. on Comp. Geom., (2003)256--263.
Pseudo Approximation Algorithms with Applications to Optimal Motion Planning
T. Asano, D. Kirkpatrick, C. Yap
Discrete and Comp. Geom, 31:1(2004)139-171. Special Conference Issue of 18th ACM Symp. on Comp. Geom. (2002).
Robust Geometric Computation
C. Yap, Chapter 41 in CRC Handbook, (Eds. J.E.Goodman and J.O'Rourke), pp.927--952, 2004. (Revised and expanded version of the 1997 version)
Hypergeometric Functions in Exact Geometric Computation
Z. Du and M. Eleftheriou and J. Moreira and C. Yap
Electronic Notes in Theoretical Computer Science, 66:1 (2002). Proceedings, Fifth Workshop on Computability and Complexity in Analysis, Malaga, Spain. July 12-13, 2002.
Towards Robust Geometric Computation
Chee Yap and Kurt Mehlhorn
Fundamentals of Computer Science Study Conference, July 25-27, 2001, Washington DC. White Paper. Conference sponsored by Computer Science and Telecommunications Board (CSTB) and NSF.
Recent Progress in Exact Geometric Computation
C. Li, S. Pion and C. Yap (June, 2001)
J. of Logic and Algebraic Programming, Special Issue on Practical Development of Exact Real Number Computation (eds. N.Mueller, M.Escardo, P.Zimmermann), 64:1(2005)85--111. Also, DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, (Mar 12-16, 2001).
Exact Geometric Computation: Theory and Applications
Chen Li, PhD Thesis (Jan, 2001)
QuickMul: Practical FFT-based Integer Multiplication
C. Yap and C. Li (Oct, 2000).
Download our implementation.
A New Constructive Root Bound for Algebraic Expressions
C. Li and C. Yap. Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA), (2001)496--505.
Randomized Zero Testing of Radical Expressions and Elementary Geometry Theorem Proving
D. Tulone, C. Yap and C. Li (June, 2000). Proc. ADG'00, Zurich Sep 25-27, 2000. Also, LNCS/LNAI 2061, Springer 2001.
A Core Library for Robust Numeric and Geometric Computation
V. Karamcheti, C. Li, I. Pechtchanski and C. Yap. 15th ACM Symp. on Comp.Geometry, (1999)351--359.
Tutorial for CORE Library
C. Li, C. Yap, S. Pion, Z. Du, V. Sharma (June, 2003) (original 1999 version )
A New Number Core for Robust Numerical and Geometric Libraries
C. Yap (Oct, 1998)
Invited talk, Workshop on Computational Geometry, Brown University, 1998.
Precision-sensitive Euclidean shortest path in 3-space
J. Choi, J. Sellen and C. Yap,
11th ACM SCG (1995) 350--359. In SIAM J.Comp., 29(2000)1577-1595.
Real/Expr: Implementation of an Exact Computation Package
Kouji Ouchi, Masters Thesis, New York University (Jan, 1997)
The Exact Computation Paradigm
Chee K. Yap and Thomas Dub\'e,
in ``Computing in Euclidean Geometry'' (eds. D.-Z. Du and F. K. Hwang) World Scientific Press, Singapore. 2nd edition, pp.452--486, 1995.
Towards Exact Geometric Computation
Chee K. Yap, CGTA 7(1997)3-23.