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
Theory of Complexity Classes
Chee Yap
Here is a link from
Electronic Colloquium on Computational Complexity (ECCC).
Online since 1987. Papers and ThesesSubdivision methods for sumofdistances Problems: FermatWeber point, nellipses and the minsum cluster Voronoi diagram
I. Mantas, E. Papadopoulou, M. Suderland and C. Yap.
38th SoCG (Media Expo), Berlin, Germany. Jun 710, 2022. [ Click here ] for accompanying video. Certified Approximation Algorithms for the Fermat Point and nEllipses [ long version]
K.Junginger, I.Mantas E.Papadopoulou,
M.Suderland and C. Yap.
Proc. 29th ESA, Lisbon, Portugal. Sep 68, 2021. Novel Range Functions via Taylor Expansions and Recursive Lagrange Interpolation, with application to Real Root Isolation
Kai Hormann, Lucas Kania and Chee Yap
Proc. 46th ISSAC, Saint Petersburg. July 1823, 2021. Download [software in Core Library] (use "guest" as username and password) The Dplus Discriminant and BitComplexity of Root Clustering
Jing Yang and Chee Yap
[ arXiv:2105.03856[cs.SC]], May 2021. On muSymmetric Polynomials
Jing Yang and Chee Yap
J.Algebra and its Applications. [DOI] (2021). Download Maple Software from [ GitHub] Also in [ arXiv:2001.07403[cs.SC]], Mar 2020. Towards Soft Exact Computation
Chee Yap
Invited paper for Computer Algebra in Scientific Computing: 21st Workshop (CASC 2019). Plekhanov Russian Univ of Economics, Moscow. Aug 2630, 2019. LNCS Vol.11661 (pp.1236). Effective Subdivision Algorithm for Isolating Zeros of Real Systems of Equations, with Complexity Analysis
Rémi Imbach and Marc Pouget and Chee Yap
Computer Algebra in Scientific Computing: 21st Workshop (CASC 2019). [ Core Library software in SVN] Plekhanov Russian Univ of Economics, Moscow. Aug 2630, 2019. In Math.Comp.Sci. (online Jun 17, 2020). DOI. RootFinding with Implicit Inflation
R. Imbach, V.Y. Pan, C. Yap, I.S. Kotsireas and V. Zaderman
Computer Algebra in Scientific Computing: 21st Workshop (CASC 2019). Plekhanov Russian Univ of Economics, Moscow. Aug 2630, 2019. In LNCS Vol.11661, pp.236245. SpringerVerlag. DOI. Algorithmic Approach to Small Limit Cycles of Nonlinear Differential Systems: the Averaging Method Revisited
Bo Huang and Chee Yap
Proc. 44th ISSAC, Beihang University, Beijing. July 1518, 2019. In Special Issue of J.Symbolic Compulation (2020). [DOI] [ Link to Maple Software in Github] Effective Subdivision Algorithm for Isolating Zeros of Real Systems of Equations, with Complexity Analysis
Juan Xu and Chee Yap
Proc. 44th ISSAC, Beihang University, Beijing. July 1518, 2019. Rods and Rings: Soft Subdivision Planner for R^3x S^2
Tom Hsu and YiJen Chiang and Chee Yap
Proc. 35th SoCG, Portland, Oregon. June 1821, 2019. Global Identifiability of Differential Models
H. Hong, A. Ovchinnikov, G. Pogudin and C. Yap
Communic. Pure & Applied Math Vol.73, No.9, pages 18311879, 2020. DOI. Also ArXiv 1801.08112. math.CA, Jan 2018. SIAN: Software for Structural Identifiability Analysis of ODE Models [[ Supplementary Data]]
H. Hong, A. Ovchinnikov, G. Pogudin and C. Yap
Bioinformatics: Systems Biology, Application Note Section vol. 12, Jan 2019. DOI. Soft Subdivision Motion Planning for Complex Planar Robots
B. Zhou, Y.J. Chiang and C. Yap
Comp.Geom., Vol.29, 2021. https://doi.org/10.1016/j.comgeo.2020.101683 (Also: Proc. 26th ESA, Helsinki. Aug 2024, 2018.) An Approach for Certifying Homotopy Continuation Paths: Univariate Case
J. Xu, M. Burr and C. Yap
ISSAC 2018. Proc. 43rd ISSAC, CUNY Graduate Center, New York City. July 1619, 2018. On muSymmetric Polynomials and Dplus
Jing Yang and Chee Yap
ICMS 2018. 6th Int'l Congress on Mathematical Software. University of Notre Dame. July 2427, 2018. Implementation of a NearOptimal Complex Root Clustering Algorithm
Rémi Imbach, Victor Pan and Chee Yap
ICMS 2018. 6th Int'l Congress on Mathematical Software. University of Notre Dame. July 2427, 2018. [ Core Library software in SVN] On Quadtrees, Voronoi Diagrams, and Lattices: Results in Geometric Algorithms
Huxley David Bennett
PhD Thesis (Sep 2017) ResolutionExact Planner for Thick NonCrossing 2Link Robots
C. Yap, Z. Luo and C.H. Hsu
Proc.~13th WAFR, San Francisco, Dec 2016. See Algorithmic Foundations of Robotics XII, pp.576591, Springer 2020. Planar Minimization Diagrams via Subdivision, with Application to Anisotropic Voronoi Diagrams [ with Reproducibility certificate ]
H. Bennett, E. Papadopoulou, and C. Yap
Eurographics Symposium on Geometric Processing Vol.35, No.5, 2016. Berlin, Germany. June 2024, 2016. Path Planning for Simple Robots using Soft Subdivision Search [ accompanying Video SoCG2016 ]
C.H. Hsu, J.P. Ryan, and C. Yap
Multimedia Exposition. Proc. 32nd SoCG, Boston, MA. June 1418, 2016. Complexity Analysis of Root Clustering for a Complex Polynomial (Full paper with proofs in Appendices in [ arXiv:2105.05183[cs.SC] ])
R.Becker, M.Sagraloff, V.Sharma, J.Xu and C.Yap
Proc. 41st ISSAC, Waterloo, Canada. July 1922, 2016. Juan Xu won the Distinguised Female Student Award for this work. 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
J.Symbolic Computation Vol.86, pp.5196, 2018. Also: ArXiv eprints arXiv:1509.06231v3 [cs.NA]}. Jan 2016. 51 pages. 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. In LNCS Vol.9130 (pp.722). Isotopic Arrangement of Simple Curves: an Exact Numerical Approach based on Subdivision [This version has appendices 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. LNCS Vol. 8592, pp.277282, Springer. [This arXiv:2009.00811 version also has the appendices.] 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 Quadtrees in All Dimensions
Huck Bennett and Chee Yap.
CGTA Vol.63, pp.2039, 2017. Also: 14th SWAT. July 24 2014. Copenhagen, Denmark. LNCS Vol. 8503, pp.3849, Springer. [ 2Dimensional Version Only]: 23rd 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. Springer Tracts in Advanced Robotics (STAR) Vol.107, pp.352370. 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'' in Computability in Europe (CiE 2013), Milan, Italy, July 15, 2013. LNCS Vol.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 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
Chee Yap, Vikram Sharma and JyhMing Lien.
Invited Talk at 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. Pages 319326. 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. Also: J.Symbolic Computation Vol.78, pp.34, 2017. 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 )]
M. Sagraloff and C. Yap
Proc. 36th ISSAC, San Jose, California. June 811, 2011. Pages 353360. Empirical Study of an EvaluationBased Subdivision Algorithm for Complex Root Isolation
N. Kamath, I. Voiculescu and C. 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 )]
[(
Full Paper of TAMC 2011 )] with new section
on Robustness Results (updated: 18 Aug 2020)
C. Yap
Proc. Theory and Applications of Models of Computation (TAMC 2011), May 2325, 2011, Tokyo, Japan. LNCS Vol.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 Vol.6327, 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 of 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
Based on invited talk for 3rd Workshop on Algorithms and Computation(WALCOM 2009). Kolkata, India, Feb 1820, 2009. In: LNCS Vol.5431, pp.1531, 2009. SpringerVerlag. Complete Subdivision Algorithms, II: Isotopic Meshing of Singular Algebraic Curves [ Full Version]
M. Burr, S.W. Choi, B. Galehouse, C. 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
LNCS Vol.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] 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 SoCG 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. A Practical Study and Evaluation of Libraries for Exact Geometric Computing
Alexander Schneider
Masters Thesis at University of Salzburg (June, 2002) 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 Vol.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. Based on invited talk, 5th CCCG (1993) Waterloo, Canada.
http://cs.nyu.edu/yap/papers/index.html
(not actively maintained)
