Introduction People Papers Talks Links Wiki 
BooksRobust Geometric Computation (Draft)
Kurt Mehlhorn and Chee Yap
Fundamental Problems in Algorithmic Algebra
Chee Yap
Oxford University Press, 2000
Papers and ThesesPlanar Minimization Diagrams via Subdivision, with Application to Anisotropic Voronoi Diagrams [ reproducibility certificate]
H.Bennett, E.Papadopoulou, and C.Yap
Eurographics Symposium on Geometric Processing, Volume 35, No.5, 2016. Berlin, Germany. June 2024, 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 1418, 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 1922, 2016. A Simple NearOptimal Subdivision Algorithm for Complex Root Isolation based on Pellet Test and Newton Iteration
R.Becker, M.Sagraloff, V.Sharma and C.Yap
ArXiv eprints, 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 35, 2015. Guilin, China. LNCS Volume 9130 (pp.722). ResolutionExact Planner NonCrossing 2Link Robot
Zhongdi Luo and Chee K. Yap
Submitted (Feb 2014) 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 MKTest to confirm roots.)
JyhMing Lien, Vikram Sharma, Gert Vegter and Chee Yap 4th Intl. Congress on Mathematical Software (ICMS). Aug 59, 2014. Seoul, Korea. In LNCS Vol. 8592, pp.277282, Springer. ResolutionExact Planner for a 2Link Planar Robot using Soft Predicates
Zhongdi Luo.
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 24 2014. Copenhagen, Denmark. LNCS Vol. 8503, pp.3849, Springer. Journal version accepted in CGTA (2016). 2Dimensional version, [Amortized Analysis of Balanced Quadtrees]: 23rd Annual Fall Workshop on Comp. Geometry (FWCG), The City College of NY. Oct 2526, 2013. ResolutionExact Algorithms for Link Robots
Zhongdi Luo, YiJen Chiang, JyhMing Lien, and Chee Yap.
11th Int'l Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), 35 August 2014, Bogazici University, Istanbul, Turkey. [Preliminary version]: 23rd Annual Fall Workshop on Computational Geometry (FWCG), The City College of New York. Oct 2526, 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 15, 2013. LNCS No. 7921, pp. 434444. Soft Subdivision Search and Motion Planning
Chee Yap
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, YiJen Chiang and Chee Yap
Proc. 29th SoCG, Rio de Janeiro, Brazil. June 1720, 2013. Also: CGTA (Special Issue for SoCG'13) Vol.48, No.8, pp.589605, 2015. Lightly edited original [ IROS poster version] IROS 2011 Workshop on Progress and Open Problems in Motion Planning, (Sep 30, 2011, San Francisco). NonLocal Isotopic Approximation of Nonsingular Surfaces
Long Lin, Chee Yap, and Jihun Yu
ComputerAided Design, Vol. 45, No. 2, pages 451462, 2013. Proc.Symp. on Solid and Physical Modeling (SPM). University of Burgundy, Dijon, France. Oct 2931, 2012. Towards Exact Numerical Voronoi Diagrams (Invited Talk)
Chee Yap, Vikram Sharma and JyhMing Lien.
Proc. 9th Intl. Symp. on Voronoi Diagrams in Science and Engineering (ISVD), IEEE Publisher. Pages 216. Rutgers University, NJ. Jun 2729, 2012. http://dx.doi.org/10.1109/ISVD.2012.31 Near Optimal Tree Size Bounds on a Simple Real Root Isolation Algorithm
Vikram Sharma and Chee Yap
Proc. 37th ISSAC, Grenoble, France. July 2225, 2012. Certified Computation of Planar MorseSmale Complexes of Smooth Functions
Amit Chattopadhyay and Gert Vegter and Chee Yap
Proc. 28th SoCG, Chapel Hill, NC. June 1620, 2012. Pages 259268. 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 1318, 2012. Computer Graphics Forum, Vol.31, No.2, pp.815824. Surface Representation of Particle Based Fluids
Jihun Yu
PhD Thesis (Sep 2011) Adaptive Isotopic Approximation of Nonsingular Curves and Surfaces A Simple But Exact and Efficient Algorithm for Complex Root Isolation and its Complexity Analysis See also an alternative
[
The 8Point Test Version]
Michael Sagraloff and Chee Yap
Proc. 36th ISSAC, San Jose, California. June 811, 2011. Pages 353360. Empirical Study of an EvaluationBased 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 79, 2011. pages 155164. A Real Elementary Approach to the Master Theorem and Generalizations [ Slides for TAMC talk]
C. Yap
Proc. Theory and Applications of Models of Computation (TAMC 2011), May 2325, 2011, Tokyo, Japan. LNCS No. 6648, pp.1426. Reconstructing Surfaces of ParticleBased Fluids Using Anisotropic Kernels
Jihun Yu and Greg Turk
Proc. of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 217225, Madrid, Spain, 2010 (Jihun won the second best paper award.) Subdivision Algorithms for Complex Root Isolation: Empirical Comparisons
Narayan Kamath
Masters Thesis, Oxford University, August 2010. Pi is in Log Space
C. Yap
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 1317, 2010. LNCS 6327, Springer 2010, pp.121141. Continuous Amortization: A NonProbabilistic 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
Benjamin Galehouse
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, SpringerVerlag, pp.308407. 2009. Tutorial: Exact Numerical Computation in Algebra and Geometry [3in1 Talk] [Talk 1] [Talk 2] [Talk 3]
Chee K. Yap
Proceedings, 34th ISSAC, pp.387388. KIAS, Seoul, Korea. Aug 2831, 2009. Lower Bounds for ZeroDimensional Projections
W.Dale Brownawell and Chee K. Yap
Proceedings, 34th ISSAC, pp. 7986. KIAS, Seoul, Korea. Aug 2831, 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.760795, 2011. (Special Issue based on 25th ACM Symp. Computational Geometry (SoCG), in Aarhus, Denmark, Jun 810, 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 1820, 2009. In: Lecture Notes in Computer Science No.5431, pp.1531, 2009. SpringerVerlag. 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.8794. Hagenberg, Austria, Jul 2023, 2008. J. Symbolic Computation (Special Issue), Vol.47, No.2, pp.131152 (2012). Complete Numerical Isolation of Real Zeros in General Triangular Systems
JinSan Cheng, XiaoShan Gao, Chee Yap
Proc. Intl. Symp. on Symbolic & Algebraic Computation (ISSAC 2007), Waterloo, Canada, Jul 29Aug 1, 2007. J. Symbolic Computation (Special Issue), Vol.44, No.7, pp.768785, (2009). Complexity Analysis of Algorithms in Algebraic Computation
Vikram Sharma
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
Chee Yap
Lecture Notes in CS No.5045, pp. 193237, Springer (2008). Based on talk at Dagstuhl Seminar on ``Reliable Implementation of Real Number Algorithms: Theory and Practice'', Jan 813, 2006. Is It Really Zero?
Chee Yap
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 912, 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 68, 2006. pp.217226. Decidability of Collision between a Helical Motion and an Algebraic Motion
Sung Woo Choi, Sungil Pae, Hyungju Park and Chee Yap
Proc. 7th Conference on Real Numbers & Computers (RNC 7) LORIA, Nancy, France, Jul 1012, 2006. Guaranteed Precision for Transcendental and Algebraic Computation made Easy
Zilin Du
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 36, 2005. (SpringerLink) Amortized Bound for Root Isolation Via Sturm Sequences
Zilin Du, Vikram Sharma and Chee Yap
Proc. SymbolicNumeric Computation (SNC'05), Xi'an, China, Jul 1921, 2005. Also: in ``SymbolicNumeric Computation'' (eds. D. Wang and L. Zhi), Birkhauser Verlag AG, Basel, pp. 113130, 2007. (ISBN 9783764379834) 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.246249. 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:56(2006)567590. Also: 21st ACM Symp. on Comp. Geom., (2005)116125. 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)6178. Also, Proc. European Symposium on Algorithms (ESA), Nov 2004. On Guaranteed Accuracy Computation
C. Yap
Chapter 12 in book "Geometric Computation'', Falai Chen and Dongming Wang (Eds.). World Scientific Pub.Co., pp.322373, 2004. Constructive Root Bound Method for kAry Rational Input Numbers S.
Pion and C. Yap
Theoretical Computer Science 269:13(2006)361376. DOI link. Also: 19th ACM Symp. on Comp. Geom. (2003)256263. Pseudo Approximation Algorithms with Applications to Optimal Motion Planning T.
Asano, D. Kirkpatrick, C. Yap
J.Discrete & Comp. Geom., 31:1(2004)139171) (Special Conference Issue) Also: Proc. 19th ACM Symp. on Comp. Geom., (2002)170178. Robust Geometric Computation
C. Yap,
Chapter 41 in CRC Handbook of Computational and Discrete Geometry. (Eds. J.E.Goodman and J.O'Rourke), pp.927952, 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 1213, 2002. Towards Robust Geometric Computation
Chee Yap and Kurt Mehlhorn
Fundamentals of Computer Science Study Conference,
July 2527, 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) 85111.
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 Chen Li,
PhD Thesis (Jan, 2001) QuickMul: Practical FFTbased Integer Multiplication A New Constructive Root Bound for Algebraic Expressions C.
Li and C. Yap,
Proc. 12th ACMSIAM Symp. on Discrete Algorithms (SODA), (2001)496505. Randomized Zero Testing of Radical Expressions and Elementary Geometry Theorem Proving D.
Tulone, C. Yap and C. Li.,
Proc. ADG'00, Zurich Sep 2527, 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)351359. Tutorial for CORE Library A New Number Core for Robust Numerical and Geometric Libraries
C. Yap
Invited talk, 3rd (CGC) Workshop on Computational Geometry, Brown University, Oct 1998. Precisionsensitive Euclidean Shortest Path in 3space J.
Choi, J. Sellen and C. Yap,
11th ACM SCG (1995) 350359. In SIAM J.Comp., 29(2000)15771595. Approximate Euclidean Shortest Paths in 3space J.
Choi, J. Sellen and C. Yap,
10th ACM SCG (1994) 4148. In IJCGA 7:4(1997)271295. Real/Expr: Implementation of an Exact Computation Package Kouji Ouchi,
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.452486, 1995. Towards Exact Geometric Computation
Chee K. Yap,
CGTA 7(1997)323. Invited talk, 5th CCCG (1993) Waterloo, Canada.
http://cs.nyu.edu/yap/papers/index.html (not actively maintained)
