{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:26:24Z","timestamp":1760369184521,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,17]],"date-time":"2013-06-17T00:00:00Z","timestamp":1371427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,6,17]]},"DOI":"10.1145\/2462356.2462386","type":"proceedings-article","created":{"date-parts":[[2014,1,7]],"date-time":"2014-01-07T17:18:46Z","timestamp":1389115126000},"page":"349-358","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["On soft predicates in subdivision motion planning"],"prefix":"10.1145","author":[{"given":"Cong","family":"Wang","sequence":"first","affiliation":[{"name":"Polytechnic Institute of NYU, Brooklyn, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi-Jen","family":"Chiang","sequence":"additional","affiliation":[{"name":"Polytechnic Institute of NYU, Brooklyn, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chee","family":"Yap","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.370502"},{"key":"e_1_3_2_1_2_1","first-page":"39","volume-title":"Proc. Intelligent Robots and Systems 95","volume":"3","author":"Barbehenn M.","unstructured":"M. Barbehenn and S. Hutchinson . Toward an exact incremental geometric robot motion planner . In Proc. Intelligent Robots and Systems 95 ., vol. 3 , pp. 39 -?44, 1995. M. Barbehenn and S. Hutchinson. Toward an exact incremental geometric robot motion planner. In Proc. Intelligent Robots and Systems 95., vol. 3, pp. 39-?44, 1995."},{"key":"e_1_3_2_1_3_1","first-page":"221","volume-title":"Handbook on Randomized Computing","author":"Bohlin R.","unstructured":"R. Bohlin and L. Kavraki . A randomized algorithm for robot path planning based on lazy evaluation . In Handbook on Randomized Computing , pp. 221 -?249. Kluwer Academic Pub., 2001. R. Bohlin and L. Kavraki. A randomized algorithm for robot path planning based on lazy evaluation. In Handbook on Randomized Computing, pp. 221-?249. Kluwer Academic Pub., 2001."},{"key":"e_1_3_2_1_4_1","volume-title":"Robot Motion: Planning and Control","author":"Brady M.","year":"1982","unstructured":"M. Brady , J. Hollerbach , T. Johnson , T. Lozano-Perez , and M. Mason . Robot Motion: Planning and Control . MIT Press , 1982 . M. Brady, J. Hollerbach, T. Johnson, T. Lozano-Perez, and M. Mason. Robot Motion: Planning and Control. MIT Press, 1982."},{"key":"e_1_3_2_1_5_1","first-page":"806","volume-title":"Proc. 8th IJCAI","volume":"2","author":"Brooks R. A.","year":"1983","unstructured":"R. A. Brooks and T. Lozano-Perez . A subdivision algorithm in configuration space for findpath with rotation . In Proc. 8th IJCAI Vol. 2 , pp. 799?- 806 , San Francisco , 1983 . Morgan Kaufmann Pub. Inc. R. A. Brooks and T. Lozano-Perez. A subdivision algorithm in configuration space for findpath with rotation. In Proc. 8th IJCAI Vol. 2, pp. 799?-806, San Francisco, 1983. Morgan Kaufmann Pub. Inc."},{"key":"e_1_3_2_1_6_1","volume-title":"TR09(136)","author":"Burr M.","year":"2009","unstructured":"M. Burr , F. Krahmer , and C. Yap . Continuous amortization: A non-probabilistic adaptive analysis technique. Electronic Colloquium on Computational Complexity (ECCC) , TR09(136) , December 2009 . M. Burr, F. Krahmer, and C. Yap. Continuous amortization: A non-probabilistic adaptive analysis technique. Electronic Colloquium on Computational Complexity (ECCC), TR09(136), December 2009."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.5.504"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064112"},{"key":"e_1_3_2_1_9_1","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"Choset H.","year":"2005","unstructured":"H. Choset , K. M. Lynch , S. Hutchinson , G. Kantor , W. Burgard , L. E. Kavraki , and S. Thrun . Principles of Robot Motion: Theory, Algorithms, and Implementations . MIT Press , Boston , 2005 . H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Boston, 2005."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(95)00016-Y"},{"key":"e_1_3_2_1_11_1","volume-title":"Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds. Algorithmica, 14: 443-?479","author":"Donald B.","year":"1995","unstructured":"B. Donald and P. Xavier . Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds. Algorithmica, 14: 443-?479 , 1995 . B. Donald and P. Xavier. Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds. Algorithmica, 14:443-?479, 1995."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"e_1_3_2_1_13_1","unstructured":"GNU MP Homepage Since 1991. GNU MP (=GMP) is a free library for arbitrary precision arithmetic. URL http:\/\/gmplib.org.  GNU MP Homepage Since 1991. GNU MP (=GMP) is a free library for arbitrary precision arithmetic. URL http:\/\/gmplib.org."},{"key":"e_1_3_2_1_14_1","first-page":"778","volume-title":"J. E. Goodman and J. O'Rourke","author":"Halperin D.","unstructured":"D. Halperin , L. Kavraki , and J.-C. Latombe . Robotics . In J. E. Goodman and J. O'Rourke , editors, Handbook of Discrete and Computational Geometry , chapter 41, pages 755?- 778 . CRC Press LLC, 1997. D. Halperin, L. Kavraki, and J.-C. Latombe. Robotics. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 41, pages 755?-778. CRC Press LLC, 1997."},{"key":"e_1_3_2_1_16_1","series-title":"LNCS","first-page":"409","volume-title":"Algorithms ? ESA","author":"Hemmer M.","year":"2010","unstructured":"M. Hemmer , O. Setter , and D. Halperin . Constructing the exact Voronoi diagram of arbitrary lines in three-dimensional space . In Algorithms ? ESA 2010 , vol. 6346 of LNCS , pp. 398?- 409 . Springer 2010. M. Hemmer, O. Setter, and D. Halperin. Constructing the exact Voronoi diagram of arbitrary lines in three-dimensional space. In Algorithms ? ESA 2010, vol. 6346 of LNCS, pp. 398?-409. Springer 2010."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906067174"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/532147"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning Algorithms","author":"LaValle S. M.","year":"2006","unstructured":"S. M. LaValle . Planning Algorithms . Cambridge University Press , Cambridge , 2006 . S. M. LaValle. Planning Algorithms. Cambridge University Press, Cambridge, 2006."},{"key":"e_1_3_2_1_21_1","unstructured":"R. E. Moore. Interval Analysis. Prentice Hall Englewood Cliffs NJ 1966.  R. E. Moore. Interval Analysis. Prentice Hall Englewood Cliffs NJ 1966."},{"key":"e_1_3_2_1_22_1","unstructured":"MPFR Homepage Since 2000. URL http:\/\/www.mpfr.org\/. MPFR is a C++-library for multi-precision floating-point computation with exact rounding modes.  MPFR Homepage Since 2000. URL http:\/\/www.mpfr.org\/. MPFR is a C++-library for multi-precision floating-point computation with exact rounding modes."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90021-5"},{"key":"e_1_3_2_1_24_1","first-page":"3711","volume-title":"IEEE ICRA","author":"Plaku E.","unstructured":"E. Plaku , K. Bekris , and L. Kavraki . OOPS for motion planning: An online open-source programming system . In IEEE ICRA , pp. 3711 -?3716, 2007. E. Plaku, K. Bekris, and L. Kavraki. OOPS for motion planning: An online open-source programming system. In IEEE ICRA, pp. 3711-?3716, 2007."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798331975"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993886.1993938"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2040572.2040627"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160360305"},{"key":"e_1_3_2_1_29_1","volume-title":"On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math., 4: 298-?351","author":"Schwartz J. T.","year":"1983","unstructured":"J. T. Schwartz and M. Sharir . On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math., 4: 298-?351 , 1983 . J. T. Schwartz and M. Sharir. On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math., 4:298-?351, 1983."},{"key":"e_1_3_2_1_30_1","series-title":"Ablex Series in Artificial Intelligence","volume-title":"Planning, Geometry and Complexity of Robot Motion","author":"Schwartz J. T.","year":"1987","unstructured":"J. T. Schwartz , M. Sharir , and J. Hopcroft , editors . Planning, Geometry and Complexity of Robot Motion . Ablex Series in Artificial Intelligence . Ablex Publishing Corp ., Norwood, New Jersey, 1987 . J. T. Schwartz, M. Sharir, and J. Hopcroft, editors. Planning, Geometry and Complexity of Robot Motion. Ablex Series in Artificial Intelligence. Ablex Publishing Corp., Norwood, New Jersey, 1987."},{"key":"e_1_3_2_1_31_1","first-page":"483","article-title":"Generalized Voronoi diagrams for moving a ladder I: topological analysis","author":"Sharir M.","year":"1986","unstructured":"M. Sharir , C. O'D' ?unlaing, and C. Yap . Generalized Voronoi diagrams for moving a ladder I: topological analysis . Communications in Pure and Applied Math. , XXXIX :423?- 483 , 1986 . M. Sharir, C. O'D' ?unlaing, and C. Yap. Generalized Voronoi diagrams for moving a ladder I: topological analysis. Communications in Pure and Applied Math., XXXIX:423?-483, 1986.","journal-title":"Communications in Pure and Applied Math."},{"key":"e_1_3_2_1_32_1","volume-title":"Generalized Voronoi diagrams for moving a ladder II: efficient computation of the diagram. Algorithmica, 2: 27-?59","author":"Sharir M.","year":"1987","unstructured":"M. Sharir , C. O'Dunlaing , and C. Yap . Generalized Voronoi diagrams for moving a ladder II: efficient computation of the diagram. Algorithmica, 2: 27-?59 , 1987 . M. Sharir, C. O'Dunlaing, and C. Yap. Generalized Voronoi diagrams for moving a ladder II: efficient computation of the diagram. Algorithmica, 2:27-?59, 1987."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442829.2442875"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057432.1057464"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2005.11.003"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVD.2012.31"},{"key":"e_1_3_2_1_37_1","series-title":"Advances in Robotics","first-page":"95","volume-title":"Algorithmic and geometric issues","author":"Yap C. K.","unstructured":"C. K. Yap . Algorithmic motion planning . In J. Schwartz and C. Yap, editors, Advances in Robotics , Vol. 1 : Algorithmic and geometric issues , volume 1, pages 95 -?143. Lawrence Erlbaum Associates, 1987. C. K. Yap. Algorithmic motion planning. In J. Schwartz and C. Yap, editors, Advances in Robotics, Vol. 1: Algorithmic and geometric issues, volume 1, pages 95-?143. Lawrence Erlbaum Associates, 1987."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187890"},{"key":"e_1_3_2_1_39_1","first-page":"952","volume-title":"J. E. Goodman and J. O'Rourke","author":"Yap C. K.","unstructured":"C. K. Yap . Robust geometric computation . In J. E. Goodman and J. O'Rourke , editors, Handbook of Discrete and Computational Geometry , chapter 41, pages 927?- 952 . Chapman & Hall\/CRC, Boca Raton, FL, 2nd edition, 2004. C. K. Yap. Robust geometric computation. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 41, pages 927?-952. Chapman & Hall\/CRC, Boca Raton, FL, 2nd edition, 2004."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03456-5_26"},{"volume-title":"April 20, 2012: Symp. on Geometric Processing (SGP).","author":"Yap C. K.","key":"e_1_3_2_1_41_1","unstructured":"C. K. Yap . Theory of Soft Subdivision Search and Motion Planning, 2012 . Submitted, April 20, 2012: Symp. on Geometric Processing (SGP). C. K. Yap. Theory of Soft Subdivision Search and Motion Planning, 2012. Submitted, April 20, 2012: Symp. on Geometric Processing (SGP)."},{"key":"e_1_3_2_1_42_1","volume-title":"Efficient cell labelling and path non-existence computation using C-obstacle query. Int'l. J. Robotics Research, 27(11?-12)","author":"Zhang L.","year":"2008","unstructured":"L. Zhang , Y. J. Kim , and D. Manocha . Efficient cell labelling and path non-existence computation using C-obstacle query. Int'l. J. Robotics Research, 27(11?-12) , 2008 . L. Zhang, Y. J. Kim, and D. Manocha. Efficient cell labelling and path non-existence computation using C-obstacle query. Int'l. J. Robotics Research, 27(11?-12), 2008."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.68066"}],"event":{"name":"SoCG '13: Symposium on Computational Geometry 2013","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rio de Janeiro Brazil","acronym":"SoCG '13"},"container-title":["Proceedings of the twenty-ninth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2462356.2462386","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2462356.2462386","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:29Z","timestamp":1750234709000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2462356.2462386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,17]]},"references-count":42,"alternative-id":["10.1145\/2462356.2462386","10.1145\/2462356"],"URL":"https:\/\/doi.org\/10.1145\/2462356.2462386","relation":{},"subject":[],"published":{"date-parts":[[2013,6,17]]},"assertion":[{"value":"2013-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}