{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:28:17Z","timestamp":1760441297665,"version":"3.41.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319196466"},{"type":"electronic","value":"9783319196473"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19647-3_2","type":"book-chapter","created":{"date-parts":[[2015,6,26]],"date-time":"2015-06-26T09:03:08Z","timestamp":1435309388000},"page":"7-22","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Soft Subdivision Search in Motion Planning, II: Axiomatics"],"prefix":"10.1007","author":[{"given":"Chee K.","family":"Yap","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,27]]},"reference":[{"key":"2_CR1","unstructured":"Barbehenn, M., Hutchinson, S.: Toward an exact incremental geometric robot motion planner. In: Proceedings of Intelligent Robots and Systems 1995, vol. 3, pp. 39\u201344 (1995). 1995 IEEE, RSJ International Conference, Pittsburgh. PA, USA, pp. 5\u20139, August 1995"},{"key":"2_CR2","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10, 2nd edn. Springer, Heidelberg (2006)","edition":"2"},{"issue":"38\u201340","key":"2_CR3","doi-asserted-by":"publisher","first-page":"3839","DOI":"10.1016\/j.tcs.2009.05.021","volume":"410","author":"O Beyersdorff","year":"2009","unstructured":"Beyersdorff, O., K\u00f6bler, J., Messner, J.: Nondeterministic functions and the existence of optimal proof systems. Theor. Comput. Sci. 410(38\u201340), 3839\u20133855 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR4","unstructured":"Brooks, R.A., Lozano-Perez, T.: A subdivision algorithm in configuration space for findpath with rotation. In: Proceedings of the 8th IJCAI, San Francisco, CA, USA, vol. 2, pp. 799\u2013806. Morgan Kaufmann Publishers Inc. (1983)"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Brownawell, W.D., Yap, C.K.: Lower bounds for zero-dimensional projections. In: 2009 34th International Symposium on Symbolic and Algebraic Computation (ISSAC 2009), pp. 79\u201386. KIAS, Seoul, Korea, 28\u201331 July 2009","DOI":"10.1145\/1576702.1576716"},{"issue":"2","key":"2_CR6","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.jsc.2011.08.022","volume":"47","author":"M Burr","year":"2012","unstructured":"Burr, M., Krahmer, F.: SqFreeEVAL: an (almost) optimal real-root isolation algorithm. J. Symb. Comput. 47(2), 153\u2013166 (2012)","journal-title":"J. Symb. Comput."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Cabello, S., Kerber, M.: Semi-dynamic connectivity in the plane. In: Algorithms and Data Structure Symposium (WADS 2015) (to appear, 2015). arXiv:1502.03690","DOI":"10.1007\/978-3-319-21840-3_10"},{"key":"2_CR8","unstructured":"Chiang, Y.-J., Yap, C.: Numerical subdivision methods in motion planning. 2011 Poster, IROS Workshop on Progress and Open Problems in Motion Planning, San Francisco, 30 September 2011"},{"key":"2_CR9","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"H Choset","year":"2005","unstructured":"Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Boston (2005)"},{"issue":"4","key":"2_CR10","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/70.508439","volume":"12","author":"L Kavraki","year":"1996","unstructured":"Kavraki, L., \u0160vestka, P., Latombe, C., Overmars, M.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566\u2013580 (1996)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"2_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning Algorithms","author":"SM LaValle","year":"2006","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)"},{"key":"2_CR12","unstructured":"Luo, Z., Chiang, Y.-J., Lien, J.-M., Yap, C.: Resolution exact algorithms for link robots. In: 2014 Proceedings of the 11th WAFR, Bo\u01e7azi\u00e7i University, Istanbul, Turkey, 3\u20135 August 2014. (to appear in a Springer Tracts in Advanced Robotics (STAR))"},{"key":"2_CR13","unstructured":"Luo, Z., Yap, C.: Resolution exact planner for non-crossing 2-link robot (2015, Submitted)"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Nowakiewicz, M.: MST-based method for 6DOF rigid body motion planning in narrow passages. In: 2010 Proceedings of IEEE\/RSJ International Conference on Intelligent Robots and Systems, Taipei, Taiwan, pp. 5380\u20135385, 18\u201322 October 2010","DOI":"10.1109\/IROS.2010.5650577"},{"key":"2_CR15","first-page":"207","volume":"15","author":"C \u00d3\u2019D\u00fanlaing","year":"1983","unstructured":"\u00d3\u2019D\u00fanlaing, C., Sharir, M., Yap, C.K.: Retraction: a new approach to motion-planning. ACM Symp. Theor. Comput. 15, 207\u2013220 (1983)","journal-title":"ACM Symp. Theor. Comput."},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/0196-6774(85)90021-5","volume":"6","author":"C \u00d3\u2019D\u00fanlaing","year":"1985","unstructured":"\u00d3\u2019D\u00fanlaing, C., Yap, C.K.: A \u201cretraction\u201d method for planning the motion of a disc. J. Algorithms 6, 104\u2013111 (1985)","journal-title":"J. Algorithms"},{"issue":"9","key":"2_CR17","doi-asserted-by":"publisher","first-page":"2218","DOI":"10.1016\/j.apnum.2008.12.011","volume":"59","author":"M-C Rivara","year":"2009","unstructured":"Rivara, M.-C.: Lepp-bisection algorithms, applications and mathematical properties. Appl. Numer. Math. 59(9), 2218\u20132235 (2009)","journal-title":"Appl. Numer. Math."},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Sagraloff, M., Yap, C.K.: A simple but exact and efficient algorithm for complex root isolation. In: Emiris, I.Z. (ed.) 36th International Symposium on Symbolic and Algebraic Computation, San Jose, California, pp. 353\u2013360, 8\u201311 June 2011","DOI":"10.1145\/1993886.1993938"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Sharma, V., Yap, C.: Near optimal tree size bounds on a simple real root isolation algorithm. In: 2012 37th International Symposium on Symbolic and Algebraic Computation (ISSAC 2012), Grenoble, France, pp. 319\u2013326, 22\u201325 July 2012","DOI":"10.1145\/2442829.2442875"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 2014 Computational Geometry: Theory and Applications, Special Issue for SoCG, Rio de Janeiro, Brazil, 17\u201320 June 2013","DOI":"10.1145\/2462356.2462386"},{"key":"2_CR21","unstructured":"Wei, Z., Yap, C.: Soft subdivision planner for a rod (2015. in preparation)"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Yap, C., Sharma, V., Lien, J.-M.: Towards exact numerical voronoi diagrams. In: 2012 9th Proceedings of the International Symposium of Voronoi Diagrams in Science and Engineering (ISVD), Rutgers University, NJ, pp. 2\u201316. IEEE, 27\u201329 June 2012. Invited Talk","DOI":"10.1109\/ISVD.2012.31"},{"key":"2_CR23","series-title":"Algorithmic and Geometric Issues","first-page":"95","volume-title":"Advances in Robotics","author":"CK Yap","year":"1987","unstructured":"Yap, C.K.: Algorithmic motion planning. In: Schwartz, J., Yap, C. (eds.) Advances in Robotics. Algorithmic and Geometric Issues, vol. 1, pp. 95\u2013143. Lawrence Erlbaum Associates, Hillsdale (1987)"},{"key":"2_CR24","first-page":"927","volume-title":"Handbook of Discrete and Computational Geometry","author":"CK Yap","year":"2004","unstructured":"Yap, C.K.: Robust geometric computation. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn, pp. 927\u2013952. Chapman & Hall\/CRC, Boca Raton (2004)","edition":"2"},{"key":"2_CR25","unstructured":"Yap, C.K.: Soft subdivision search in motion planning. In: Aladren, A., et al. (eds.) In: Proceedings of 1st Workshop on Robotics Challenge and Vision (RCV 2013), A Computing Community Consortium (CCC) Best Paper Award, Robotics Science and Systems Conference (RSS 2013), Berlin (2013). arXiv:1402.3213"},{"issue":"7","key":"2_CR26","first-page":"801","volume":"29","author":"A Yershova","year":"2010","unstructured":"Yershova, A., Jain, S., LaValle, S.M., Mitchell, J.C.: Generating uniform incremental grids on SO(3) using the Hopf fibration. IJRR 29(7), 801\u2013812 (2010)","journal-title":"IJRR"},{"issue":"11\u201312","key":"2_CR27","first-page":"1325","volume":"27","author":"L Zhang","year":"2008","unstructured":"Zhang, L., Kim, Y.J., Manocha, D.: Efficient cell labeling and path non-existence computation using C-obstacle query. Int. J. Robot. Res. 27(11\u201312), 1325\u20131349 (2008)","journal-title":"Int. J. Robot. Res."},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1109\/70.68066","volume":"7","author":"D Zhu","year":"1991","unstructured":"Zhu, D., Latombe, J.-C.: New heuristic algorithms for efficient hierarchical path planning. IEEE Trans. Robot. Autom. 7, 9\u201320 (1991)","journal-title":"IEEE Trans. Robot. Autom."}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19647-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T21:48:26Z","timestamp":1748468906000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19647-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319196466","9783319196473"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19647-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"27 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}