Introduction
People
Papers
Talks
Links
Wiki
Gallery/Videos
Features
CoreLib
Download
Contact
Books
Robust 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.
Online since 1987.
Papers and Theses
Theory and Explicit Design of a Path Planner for an SE(3) Robot
Z. Zhang, Y.J. Chiang and C. Yap.
[ arXiv:2407.05135[cs.SC]], Jul 2024.
[ arXiv:2407.05135[cs.SC]], Jul 2024.
Range Functions of Any Convergence Order and their Amortized Complexity Analysis
Kai Hormann, Chee Yap and YaShi (Andrew) Zhang.
In Computer Algebra in Scientific Computing: 25th Workshop (CASC 2023).
University of Havana, Cuba. Aug 28 - Sep 1, 2023.
Paper DOI: https://doi.org/10.1007/978-3-031-41724-5_9 (Springer LNCS).
Download [ software in Core Library] (use "guest" as username and password)
In Computer Algebra in Scientific Computing: 25th Workshop (CASC 2023).
University of Havana, Cuba. Aug 28 - Sep 1, 2023.
Paper DOI: https://doi.org/10.1007/978-3-031-41724-5_9 (Springer LNCS).
Download [ software in Core Library] (use "guest" as username and password)
Optimal Path Planning on a Semi-Dynamic Subdivision Graph
Y.-J. Chiang, D. Kirkpatrick, C. Yap and Z. Zhang.
Proc. 1st Int'l Workshop on Search and Planning with Complex Objectives (WoSePCO).
Aug 7--24, Macao, China. Workshop affiliated to IJCAI 2023.
Proc. 1st Int'l Workshop on Search and Planning with Complex Objectives (WoSePCO).
Aug 7--24, Macao, China. Workshop affiliated to IJCAI 2023.
On Certified Isotopic Approximation of Space Curves
Subdivision methods for sum-of-distances Problems: Fermat-Weber point, n-ellipses and the min-sum cluster Voronoi diagram
I. Mantas, E. Papadopoulou, M. Suderland and C. Yap.
38th SoCG (Media Expo), Berlin, Germany. Jun 7--10, 2022.
[ Click here ] for accompanying video.
38th SoCG (Media Expo), Berlin, Germany. Jun 7--10, 2022.
[ Click here ] for accompanying video.
Certified Approximation Algorithms for the Fermat Point and n-Ellipses
[ long version]
K.Junginger, I.Mantas E.Papadopoulou,
M.Suderland and C. Yap.
Proc. 29th ESA, Lisbon, Portugal. Sep 6--8, 2021.
Proc. 29th ESA, Lisbon, Portugal. Sep 6--8, 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 18--23, 2021.
Download [taylorLagrange software in Core Library] (use "guest" as username and password)
Proc. 46th ISSAC, Saint Petersburg. July 18--23, 2021.
Download [taylorLagrange software in Core Library] (use "guest" as username and password)
The D-plus Discriminant and Bit-Complexity of Root Clustering
Jing Yang and Chee Yap
[ arXiv:2105.03856[cs.SC]], May 2021.
[ arXiv:2105.03856[cs.SC]], May 2021.
On mu-Symmetric 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.
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 26-30, 2019.
LNCS Vol.11661 (pp.12--36).
Invited paper for Computer Algebra in Scientific Computing: 21st Workshop (CASC 2019).
Plekhanov Russian Univ of Economics, Moscow. Aug 26-30, 2019.
LNCS Vol.11661 (pp.12--36).
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 26-30, 2019.
In Math.Comp.Sci. (online Jun 17, 2020). DOI.
Computer Algebra in Scientific Computing: 21st Workshop (CASC 2019).
[ Core Library software in SVN]
Plekhanov Russian Univ of Economics, Moscow. Aug 26-30, 2019.
In Math.Comp.Sci. (online Jun 17, 2020). DOI.
Root-Finding 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 26-30, 2019.
In LNCS Vol.11661, pp.236--245. Springer-Verlag. DOI.
Computer Algebra in Scientific Computing: 21st Workshop (CASC 2019).
Plekhanov Russian Univ of Economics, Moscow. Aug 26-30, 2019.
In LNCS Vol.11661, pp.236--245. Springer-Verlag. 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 15-18, 2019.
In Special Issue of J.Symbolic Compulation (2020). [DOI]
[ Link to Maple Software in Github]
Proc. 44th ISSAC, Beihang University, Beijing. July 15-18, 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 15-18, 2019.
Proc. 44th ISSAC, Beihang University, Beijing. July 15-18, 2019.
Rods and Rings: Soft Subdivision Planner for R^3x S^2
Tom Hsu and Yi-Jen Chiang and Chee Yap
Proc. 35th SoCG, Portland, Oregon. June 18-21, 2019.
See also ArXiv:1903.09416 (Mar 2019) with proofs in Appendices A-F.
Proc. 35th SoCG, Portland, Oregon. June 18-21, 2019.
See also ArXiv:1903.09416 (Mar 2019) with proofs in Appendices A-F.
Global Identifiability of Differential Models
H. Hong, A. Ovchinnikov, G. Pogudin and C. Yap
Communic. Pure & Applied Math Vol.73, No.9, pages 1831-1879, 2020. DOI.
Also ArXiv 1801.08112. math.CA, Jan 2018.
Communic. Pure & Applied Math Vol.73, No.9, pages 1831-1879, 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. 1-2, Jan 2019. DOI.
Bioinformatics: Systems Biology, Application Note Section vol. 1-2, 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 20-24, 2018.)
Comp.Geom., Vol.29, 2021.
https://doi.org/10.1016/j.comgeo.2020.101683 (Also: Proc. 26th ESA, Helsinki. Aug 20-24, 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 16-19, 2018.
ISSAC 2018. Proc. 43rd ISSAC, CUNY Graduate Center, New York City. July 16-19, 2018.
On mu-Symmetric Polynomials and D-plus
Jing Yang and Chee Yap
ICMS 2018. 6th Int'l Congress on Mathematical Software. University of Notre Dame. July 24-27, 2018.
ICMS 2018. 6th Int'l Congress on Mathematical Software. University of Notre Dame. July 24-27, 2018.
Implementation of a Near-Optimal 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 24-27, 2018.
[ Core Library software in SVN]
ICMS 2018. 6th Int'l Congress on Mathematical Software. University of Notre Dame. July 24-27, 2018.
[ Core Library software in SVN]
On Quadtrees, Voronoi Diagrams, and Lattices: Results in Geometric Algorithms
Huxley David Bennett
PhD Thesis (Sep 2017)
PhD Thesis (Sep 2017)
Resolution-Exact Planner for Thick Non-Crossing 2-Link Robots
C. Yap, Z. Luo and C.-H. Hsu
Proc.~13th WAFR, San Francisco, Dec 2016.
See Algorithmic Foundations of Robotics XII, pp.576--591, Springer 2020.
Proc.~13th WAFR, San Francisco, Dec 2016.
See Algorithmic Foundations of Robotics XII, pp.576--591, 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 20-24, 2016.
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
[- accompanying Video SoCG2016 -]
C.-H. Hsu, J.P. Ryan, and C. Yap
Multimedia Exposition. Proc. 32nd SoCG, Boston, MA. June 14-18, 2016.
Multimedia Exposition. Proc. 32nd SoCG, Boston, MA. June 14-18, 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 19-22, 2016.
Juan Xu won the Distinguised Female Student Award for this work.
Proc. 41st ISSAC, Waterloo, Canada. July 19-22, 2016.
Juan Xu won the Distinguised Female Student Award for this work.
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
J.Symbolic Computation Vol.86, pp.51-96, 2018.
Also: ArXiv e-prints arXiv:1509.06231v3 [cs.NA]}. Jan 2016. 51 pages.
J.Symbolic Computation Vol.86, pp.51-96, 2018.
Also: ArXiv e-prints 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 3-5, 2015. Guilin, China.
In LNCS Vol.9130 (pp.7--22).
Plenary Talk, 9th Int'l Frontiers of Algorithmics Workshop (FAW).
Jul 3-5, 2015. Guilin, China.
In LNCS Vol.9130 (pp.7--22).
Isotopic Arrangement of Simple Curves: an Exact Numerical Approach based on Subdivision
[This version has appendices 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. LNCS Vol. 8592, pp.277--282, Springer.
[This arXiv:2009.00811 version also has the appendices.]
Aug 5-9, 2014. Seoul, Korea. LNCS Vol. 8592, pp.277--282, Springer.
[This arXiv:2009.00811 version also has the appendices.]
Resolution-Exact Planner for a 2-Link Planar Robot using Soft Predicates
Zhongdi Luo.
Masters Thesis, Department of Computer Science, Courant/NYU (Feb 2014)
Computer Science Department Master Thesis Prize.
Masters Thesis, Department of Computer Science, Courant/NYU (Feb 2014)
Computer Science Department Master Thesis Prize.
Amortized Analysis of Smooth Quadtrees in All Dimensions
Huck Bennett and Chee Yap.
CGTA Vol.63, pp.20-39, 2017.
Also: 14th SWAT. July 2-4 2014. Copenhagen, Denmark.
LNCS Vol. 8503, pp.38--49, Springer.
[ 2-Dimensional Version Only]:
23rd Fall Workshop on Comp. Geometry (FWCG), The City College of NY. Oct 25-26, 2013.
CGTA Vol.63, pp.20-39, 2017.
Also: 14th SWAT. July 2-4 2014. Copenhagen, Denmark.
LNCS Vol. 8503, pp.38--49, Springer.
[ 2-Dimensional Version Only]:
23rd 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.
Springer Tracts in Advanced Robotics (STAR) Vol.107, pp.352-370.
11th Int'l Workshop on the Algorithmic Foundations of Robotics (WAFR 2014),
3-5 August 2014, Bogazici University, Istanbul, Turkey.
Springer Tracts in Advanced Robotics (STAR) Vol.107, pp.352-370.
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 1-5, 2013. LNCS Vol.7921, pp. 434-444.
Invited paper, Special session on ``Computational Complexity in the Continuous World'' in
Computability in Europe (CiE 2013), Milan, Italy, July 1-5, 2013. LNCS Vol.7921, pp. 434-444.
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).
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 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).
Proc. 29th SoCG, Rio de Janeiro, Brazil. June 17-20, 2013.
Also: CGTA Special Issue 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.
Proc.Symp. on Solid and Physical Modeling (SPM). University of Burgundy, Dijon, France. Oct 29-31, 2012.
Towards Exact Numerical Voronoi Diagrams
Chee Yap, Vikram Sharma and Jyh-Ming Lien.
Invited Talk at
9th Intl. Symp. on Voronoi Diagrams in Science and Engineering
(ISVD),
IEEE Publisher. Pages 2--16. Rutgers University, NJ. Jun 27-29, 2012.
http://dx.doi.org/10.1109/ISVD.2012.31
IEEE Publisher. Pages 2--16. Rutgers University, NJ. Jun 27-29, 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 22-25, 2012. Pages 319-326.
Proc. 37th ISSAC, Grenoble, France. July 22-25, 2012. Pages 319-326.
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.
Also: J.Symbolic Computation Vol.78, pp.3-4-, 2017.
Proc. 28th SoCG, Chapel Hill, NC. June 16-20, 2012. Pages 259--268.
Also: J.Symbolic Computation Vol.78, pp.3-4-, 2017.
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.
33rd Eurographics, Cagliari, Italy. May 13-18, 2012.
Computer Graphics Forum, Vol.31, No.2, pp.815--824.
Surface Representation of Particle Based Fluids
Jihun Yu
PhD Thesis (Sep 2011)
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
8-Point Test Version )]
M. Sagraloff and C. Yap
Proc. 36th ISSAC, San Jose, California. June 8-11, 2011. Pages 353--360.
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
N. Kamath, I. Voiculescu and C. Yap
4th Int'l Workshop on Symbolic Numeric Computation (SNC), San Jose, California. Jun 7-9, 2011. pages 155-164.
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 )]
[(
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 23-25, 2011, Tokyo, Japan. LNCS Vol.6648, pp.14-26.
Proc. Theory and Applications of Models of Computation (TAMC 2011),
May 23-25, 2011, Tokyo, Japan. LNCS Vol.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.)
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
Narayan Kamath
Masters Thesis, Oxford University, August 2010.
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.
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 Vol.6327, pp.121--141.
3rd International Congress on Mathematical Software (ICMS), Kobe, Japan, Sep 13-17, 2010.
LNCS Vol.6327, 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.
Electronic Colloquium on Computational Complexity, TR09 Number 136, Dec 2009.
Topologically Accurate Meshing Using Domain Subdivision Techniques
Benjamin Galehouse
PhD Thesis (Sep 2009)
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.
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.
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.
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 of 25th ACM Symp. Computational Geometry (SoCG), in Aarhus, Denmark, Jun 8--10, 2009.
Click here for [ Code and Experimental Results]
Discrete & Comp.Geometry Vol.45, No.4, pp.760-795, 2011.
(Special Issue of 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
Based on invited talk for 3rd Workshop on Algorithms and Computation(WALCOM 2009).
Kolkata, India, Feb 18-20, 2009. In: LNCS Vol.5431, pp.15--31, 2009. Springer-Verlag.
Based on invited talk for 3rd Workshop on Algorithms and Computation(WALCOM 2009).
Kolkata, India, Feb 18-20, 2009. In: LNCS Vol.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, C. 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).
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).
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
Vikram Sharma
PhD Thesis (Jan, 2007)
PhD Thesis (Jan, 2007)
Degeneracy Proof Predicates for the Additively Weighted Voronoi Diagram
David L. Millman
Masters Thesis (May, 2007)
Masters Thesis (May, 2007)
Theory of Real Computation according to EGC
Chee Yap
LNCS Vol.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.
LNCS Vol.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?
Chee Yap
KIAS Magazine, No.34, Spring 2007.
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.)
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.
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.
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
Zilin Du
PhD Thesis (May, 2006)
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.
(SpringerLink)
Proc. 13th Annual European Symposium (ESA)
Palma de Mallorca, Spain, October 3-6, 2005.
(SpringerLink)
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)
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)
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.
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.
Comp.Geom.Theory and Applic. 40:1(2007)61--78.
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.322-373, 2004.
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]
Also: 19th ACM Symp. on Comp. Geom. (2003)256--263.
Theoretical Computer Science 269:1-3(2006)361-376.
[DOI]
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 SoCG Issue)
Also: Proc. 19th ACM Symp. on Comp. Geom., (2002)170--178.
J.Discrete & Comp. Geom. 31:1(2004)139--171) (Special SoCG Issue)
Also: Proc. 19th ACM Symp. on Comp. Geom., (2002)170--178.
Robust Geometric Computation
C. Yap,
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)
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.
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.
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.
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)
PhD Thesis (Jan, 2001)
QuickMul: Practical FFT-based Integer Multiplication
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.
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 Vol.2061, Springer 2001.
Proc. ADG'00, Zurich Sep 25-27, 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)351--359.
15th ACM Symp. on Comp.Geometry, (1999)351--359.
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.
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.
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.
10th ACM SCG (1994) 41--48. In IJCGA 7:4(1997)271-295.
Real/Expr: Implementation of an Exact Computation Package
Kouji Ouchi,
Masters Thesis, New York University (Jan, 1997)
Masters Thesis, New York University (Jan, 1997)
A Basis for Implementing Exact Geometric Algorithms
Thomas Dubé and Chee K. Yap,
Manuscript (Oct 15, 1993)
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.
World Scientific Press, Singapore. 2nd edition, pp.452--486, 1995.
Towards Exact Geometric Computation
Chee K. Yap
CGTA 7(1997)3-23. Based on invited talk, 5th CCCG (1993) Waterloo, Canada.
CGTA 7(1997)3-23. Based on invited talk, 5th CCCG (1993) Waterloo, Canada.
For other and older papers of Yap, not necessarily related to exact
computation, please see
http://cs.nyu.edu/yap/papers/index.html
(not actively maintained)