Robust Geometric Computation (Draft)
Kurt Mehlhorn and Chee Yap
Fundamental Problems in Algorithmic Algebra
Oxford University Press, 2000
Papers and Theses
Resolution-Exact Planner for Thick Non-Crossing 2-Link Robots
Chee K. Yap, Zhongdi Luo and Ching-Hsiang Hsu
Submitted (July 2016)
Planar Minimization Diagrams via Subdivision, with Application to Anisotropic Voronoi Diagrams [ reproducibility certificate]
H.Bennett, E.Papadopoulou, and C.Yap
Eurographics Symposium on Geometric Processing, Vol.35, No.5, 2016. Berlin, Germany. June 20-24, 2016.
Path Planning for Simple Robots using Soft Subdivision Search [ Video SoCG2016]
C.-H. Hsu, John P.Ryan, and C.Yap
Multimedia Exposition. Proc. 32nd SoCG, Boston, MA. June 14-18, 2016.
Complexity Analysis of Root Clustering for a Complex Polynomial
R.Becker, M.Sagraloff, V.Sharma, J.Xu and C.Yap
Proc. 41st ISSAC, Waterloo, Canada. July 19-22, 2016.
A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on Pellet Test and Newton Iteration
R.Becker, M.Sagraloff, V.Sharma and C.Yap
ArXiv e-prints, Sep. 2015. 51 Pages. Submitted.
Soft Subdivision Search and Motion Planning, II: Axiomatics
Chee K. Yap
Plenary Talk, 9th Int'l Frontiers of Algorithmics Workshop (FAW).
Jul 3-5, 2015. Guilin, China. LNCS Volume 9130 (pp.7--22).
Isotopic Arrangement of Simple Curves: an Exact Numerical Approach based on Subdivision
(This version has appendices not found in the proceedings, including details on the MK-Test to confirm roots.)
Jyh-Ming Lien, Vikram Sharma, Gert Vegter and Chee Yap 4th Intl. Congress on Mathematical Software (ICMS).
Aug 5-9, 2014. Seoul, Korea. In LNCS Vol. 8592, pp.277--282, Springer.
Resolution-Exact Planner for a 2-Link Planar Robot using Soft Predicates
Masters Thesis, Department of Computer Science, Courant/NYU (Feb 2014)
Computer Science Master Thesis Prize.
Amortized Analysis of Smooth Box Subdivisions in All Dimensions
Huck Bennett and Chee Yap.
14th Scandinavian Symp. and Workshop on Algorithm Theory (SWAT). July 2-4 2014. Copenhagen, Denmark.
LNCS Vol. 8503, pp.38--49, Springer.
Journal version accepted in CGTA (2016).
2-Dimensional version, [Amortized Analysis of Balanced Quadtrees]:
23rd Annual Fall Workshop on Comp. Geometry (FWCG), The City College of NY. Oct 25-26, 2013.
Resolution-Exact Algorithms for Link Robots
Zhongdi Luo, Yi-Jen Chiang, Jyh-Ming Lien, and Chee Yap.
11th Int'l Workshop on the Algorithmic Foundations of Robotics (WAFR 2014),
3-5 August 2014, Bogazici University, Istanbul, Turkey.
23rd Annual Fall Workshop on Computational Geometry (FWCG), The City College of New York. Oct 25-26, 2013.
Analytic Root Clustering: A Complete Algorithm using Soft Zero Tests
C. Yap and M. Sagraloff and V. Sharma
(Invited paper, Special session on ``Computational Complexity in the Continuous World'')
Computability in Europe (CiE 2013), Milan, Italy, July 1-5, 2013. LNCS No. 7921, pp. 434-444.
Soft Subdivision Search and Motion Planning
Proceedings, Robotics Challenge and Vision Workshop (RCV 2013),
Workshop at Robotics Science and Systems (RSS 2013), Berlin, Germany, June 27, 2013.
[RCV paper] [full paper]
This paper won the Best Paper Award at RCV. Here is the CCC blog.
Award sponsored by Computing Community Consortium (CCC).
Soft Predicates in Subdivision Motion Planning
Cong Wang, Yi-Jen Chiang and Chee Yap
Proc. 29th SoCG, Rio de Janeiro, Brazil. June 17-20, 2013.
Also: CGTA (Special Issue for SoCG'13) Vol.48, No.8, pp.589--605, 2015.
Lightly edited original [ IROS poster version]
IROS 2011 Workshop on Progress and Open Problems in Motion Planning,
(Sep 30, 2011, San Francisco).
Non-Local Isotopic Approximation of Nonsingular Surfaces
Long Lin, Chee Yap, and Jihun Yu Computer-Aided Design, Vol. 45, No. 2, pages 451--462, 2013.
Proc.Symp. on Solid and Physical Modeling (SPM). University of Burgundy, Dijon, France. Oct 29-31, 2012.
Towards Exact Numerical Voronoi Diagrams (Invited Talk)
Chee Yap, Vikram Sharma and Jyh-Ming Lien. Proc. 9th Intl. Symp. on Voronoi Diagrams in Science and Engineering (ISVD),
IEEE Publisher. Pages 2--16. Rutgers University, NJ. Jun 27-29, 2012.
Near Optimal Tree Size Bounds on a Simple Real Root Isolation Algorithm
Vikram Sharma and Chee Yap
Proc. 37th ISSAC, Grenoble, France. July 22-25, 2012.
Certified Computation of Planar Morse-Smale Complexes of Smooth Functions
Amit Chattopadhyay and Gert Vegter and Chee Yap
Proc. 28th SoCG, Chapel Hill, NC. June 16-20, 2012. Pages 259--268.
Appeared in JSC, 2016.
Explicit Mesh Surfaces for Particle Based Fluids
Jihun Yu, Chris Wojtan, Greg Turk and Chee Yap
33rd Eurographics, Cagliari, Italy. May 13-18, 2012.
Computer Graphics Forum, Vol.31, No.2, pp.815--824.
Surface Representation of Particle Based Fluids
PhD Thesis (Sep 2011)
Adaptive Isotopic Approximation of Nonsingular Curves and Surfaces
PhD Thesis (Sep 2011)
Click here for Code and Experimental Results for 3D Algorithms
A Simple But Exact and Efficient Algorithm for Complex Root Isolation and its Complexity Analysis
See also an alternative [ The 8-Point Test Version]
Michael Sagraloff and Chee Yap
Proc. 36th ISSAC, San Jose, California. June 8-11, 2011. Pages 353--360.
Empirical Study of an Evaluation-Based Subdivision Algorithm for Complex Root Isolation
Narayan Kamath, Irina Voiculescu and Chee Yap
4th Int'l Workshop on Symbolic Numeric Computation (SNC), San Jose, California. Jun 7-9, 2011. pages 155-164.
A Real Elementary Approach to the Master Theorem and Generalizations [ Slides for TAMC talk]
Proc. Theory and Applications of Models of Computation (TAMC 2011),
May 23-25, 2011, Tokyo, Japan. LNCS No. 6648, pp.14-26.
Reconstructing Surfaces of Particle-Based Fluids Using Anisotropic Kernels
Jihun Yu and Greg Turk
Proc. of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 217-225, Madrid, Spain, 2010 (Jihun won the second best paper award.)
Subdivision Algorithms for Complex Root Isolation: Empirical Comparisons
Masters Thesis, Oxford University, August 2010.
Pi is in Log Space
Manuscript, Jun 22, 2010.
See Lipton's Blog on the BBP Algorithm for Pi and on our result.
(Also Chapter 31 in ``People, Problems, Proofs'' (Essays from G\"odel's Lost Letter:2010),
by R.J.Lipton and K.W.Regan, Springer, 2013.
The Design of Core 2: A Library for Exact Numeric Computation in Geometry and Algebra
J.Yu, C. Yap, Z. Du, S.Pion, and H.Bronnimann
3rd International Congress on Mathematical Software (ICMS), Kobe, Japan, Sep 13-17, 2010.
LNCS 6327, Springer 2010, pp.121--141.
Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique
Michael Burr, Felix Krahmer, Chee Yap
Electronic Colloquium on Computational Complexity, TR09 Number 136, Dec 2009.
Topologically Accurate Meshing Using Domain Subdivision Techniques
PhD Thesis (Sep 2009)
In Praise of Numerical Computation
Chee K. Yap
in Efficient Algorithms: Essays Dedicated to K.Mehlhorn on the Occasion of his 60th Birthday,
Lecture Notes in Computer Science, No.5760, Springer-Verlag, pp.308--407. 2009.
Tutorial: Exact Numerical Computation in Algebra and Geometry [3-in-1 Talk] [Talk 1] [Talk 2] [Talk 3]
Chee K. Yap
Proceedings, 34th ISSAC, pp.387--388. KIAS, Seoul, Korea. Aug 28-31, 2009.
Lower Bounds for Zero-Dimensional Projections
W.Dale Brownawell and Chee K. Yap
Proceedings, 34th ISSAC, pp. 79--86. KIAS, Seoul, Korea. Aug 28-31, 2009.
Adaptive Isotopic Approximation of Nonsingular Curves: the Parametrizability and Nonlocal Isotopy Approach
Long Lin and Chee K. Yap
Discrete & Comp.Geometry. Vol.45, No.4, pp.760-795, 2011.
(Special Issue based on 25th ACM Symp. Computational Geometry (SoCG), in Aarhus, Denmark, Jun 8--10, 2009.
Click here for Code and Experimental Results
Foundations of Exact Rounding
Chee K. Yap and Jihun Yu
An invited talk for Proc. 3rd Workshop on Algorithms and Computation(WALCOM 2009).
Kolkata, India, Feb 18-20, 2009. In: Lecture Notes in Computer Science No.5431, pp.15--31, 2009. Springer-Verlag.
Complete Subdivision Algorithms, II: Isotopic Meshing of Singular Algebraic Curves [Full Version]
M. Burr, S.W.Choi, B. Galehouse, Chee Yap
Proc. Intl. Symp. on Symbolic & Algebraic Computation (ISSAC 2008), pp.87--94.
Hagenberg, Austria, Jul 20-23, 2008.
J. Symbolic Computation (Special Issue), Vol.47, No.2, pp.131-152 (2012).
Complete Numerical Isolation of Real Zeros in General Triangular Systems
Jin-San Cheng, Xiao-Shan Gao, Chee Yap
Proc. Intl. Symp. on Symbolic & Algebraic Computation (ISSAC 2007),
Waterloo, Canada, Jul 29-Aug 1, 2007.
J. Symbolic Computation (Special Issue), Vol.44, No.7, pp.768--785, (2009).
Complexity Analysis of Algorithms in Algebraic Computation
PhD Thesis (Jan, 2007)
Degeneracy Proof Predicates for the Additively Weighted Voronoi Diagram
David L. Millman
Masters Thesis (May, 2007)
Theory of Real Computation according to EGC
Lecture Notes in CS No.5045, pp. 193--237, Springer (2008).
Based on talk at Dagstuhl Seminar on
``Reliable Implementation of Real Number Algorithms: Theory and Practice'', Jan 8-13, 2006.
Is It Really Zero?
KIAS Magazine, No.34, Spring 2007.
Almost Tight Recursion Tree Bounds for the Descartes Method [Issac Talk Slides]
Arno Eigenwillig, Vikram Sharma and Chee Yap
Proc. Intl. Symp. on Symbolic & Algebraic Computation (ISSAC 2006),
Genova, Italy, Jul 9-12, 2006.
(Eigenwillig and Sharma won the ISSAC Best Student Author award for this paper; award shared with G.Moroz.)
Complete Subdivision Algorithms, I: Intersection of Bezier Curves
Chee K. Yap
Proc. 22nd ACM Symp. on Comp. Geom. (SoCG 2006),
Sedona, Arizona, Jun 6-8, 2006. pp.217--226.
Decidability of Collision between a Helical Motion and an Algebraic Motion
Sung Woo Choi, Sung-il Pae, Hyungju Park and Chee Yap
Proc. 7th Conference on Real Numbers & Computers (RNC 7)
LORIA, Nancy, France, Jul 10-12, 2006.
Guaranteed Precision for Transcendental and Algebraic Computation made Easy
PhD Thesis (May, 2006)
Robust Approximate Zeros
Vikram Sharma, Zilin Du and Chee Yap
Proc. 13th Annual European Symposium (ESA)
Palma de Mallorca, Spain, October 3-6, 2005.
Amortized Bound for Root Isolation Via Sturm Sequences
Zilin Du, Vikram Sharma and Chee Yap
Proc. Symbolic-Numeric Computation (SNC'05), Xi'an, China, Jul 19-21, 2005.
Also: in ``Symbolic-Numeric Computation'' (eds. D. Wang and L. Zhi),
Birkhauser Verlag AG, Basel, pp. 113--130, 2007. (ISBN 978-3-7643-7983-4)
Uniform Complexity Approximating Hypergeometric Functions with Absolute Error
Zilin Du and Chee Yap
Proc. 7th Asian Symposium on Computer Mathematics (ASCM), Eds. Sungil Pae and Hyungju Park, pp.246--249. KIAS, Seoul, Korea (Dec 2005)
Shortest Path amidst Disc Obstacles is Computable
E. Chang, S.W. Choi, D. Kwon, H. Park, C. Yap
Special Issue on Geometric Constraints, Intl.J.Comp.Geom. & Applic., 16:5-6(2006)567--590.
Also: 21st ACM Symp. on Comp. Geom., (2005)116--125.
Classroom Examples of Robustness Problems in Geometric Computation
* Here is a Companion Webpage for source code and experimental data
L.Kettner, K.Mehlhorn, S.Pion, S.Schirra, C. Yap
Comp.Geom.Theory and Applic. 40:1(2007)61--78.
Also, Proc. European Symposium on Algorithms (ESA), Nov 2004.
On Guaranteed Accuracy Computation
Chapter 12 in book "Geometric Computation'',
Falai Chen and Dongming Wang (Eds.). World Scientific Pub.Co., pp.322-373, 2004.
Constructive Root Bound Method for k-Ary Rational Input Numbers
S. Pion and C. Yap
Theoretical Computer Science 269:1-3(2006)361-376.
DOI link. Also: 19th ACM Symp. on Comp. Geom. (2003)256--263.
Pseudo Approximation Algorithms with Applications to Optimal Motion Planning
T. Asano, D. Kirkpatrick, C. Yap
J.Discrete & Comp. Geom., 31:1(2004)139--171) (Special Conference Issue)
Also: Proc. 19th ACM Symp. on Comp. Geom., (2002)170--178.
Robust Geometric Computation
Chapter 41 in CRC Handbook of Computational and Discrete Geometry.
(Eds. J.E.Goodman and J.O'Rourke), pp.927--952, 2004.
(Completely 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).
Proc. 5th Workshop on Computability and Complexity in Analysis (CCA), 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
J. of Logic and Algebraic Programming, 64:1(2004) 85--111.
Special issue on ``Practical Development of Exact Real Number Computation'',
Eds. N. Mueller and M. Escardo and P. Zimmermann.
Exact Geometric Computation: Theory and Applications
PhD Thesis (Jan, 2001)
QuickMul: Practical FFT-based Integer Multiplication
C. Yap and C. Li,
(Oct, 2000). Download the 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.,
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 here)
A New Number Core for Robust Numerical and Geometric Libraries
Invited talk, 3rd (CGC) Workshop on Computational Geometry, Brown University, Oct 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.
Approximate Euclidean Shortest Paths in 3-space
J. Choi, J. Sellen and C. Yap,
10th ACM SCG (1994) 41--48. In IJCGA 7:4(1997)271-295.
Real/Expr: Implementation of an Exact Computation Package
Masters Thesis, New York University (Jan, 1997)
A Basis for Implementing Exact Geometric Algorithms
Thomas Dubé and Chee K. Yap,
Manuscript (Oct 15, 1993)
The Exact Computation Paradigm
Chee K. Yap and Thomas Dubé ,
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. Invited talk, 5th CCCG (1993) Waterloo, Canada.
http://cs.nyu.edu/yap/papers/index.html (not actively maintained)