{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T15:31:30Z","timestamp":1771515090397,"version":"3.50.1"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030430887","type":"print"},{"value":"9783030430894","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-43089-4_40","type":"book-chapter","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T16:04:08Z","timestamp":1588781048000},"page":"624-639","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Collision Detection or Nearest-Neighbor Search? On the Computational Bottleneck in Sampling-based Motion Planning"],"prefix":"10.1007","author":[{"given":"Michal","family":"Kleinbort","sequence":"first","affiliation":[]},{"given":"Oren","family":"Salzman","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,7]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Arslan, O., Tsiotras, P.: Use of relaxation methods in sampling-based algorithms for optimal motion planning. In: ICRA. pp. 2413\u20132420 (2013)","DOI":"10.1109\/ICRA.2013.6630906"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM 45(6), 891\u2013923 (1998)","DOI":"10.1145\/293347.293348"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18, 509\u2013517 (1975)","DOI":"10.1145\/361002.361007"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edn. (2008)","DOI":"10.1007\/978-3-540-77974-2"},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"Bialkowski, J., Otte, M.W., Karaman, S., Frazzoli, E.: Efficient collision checking in sampling-based motion planning via safety certificates. I. J. Robotic Res. 35(7), 767\u2013796 (2016)","DOI":"10.1177\/0278364915625345"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Bohlin, R., Kavraki, L.E.: Path planning using lazy PRM. In: ICRA. pp. 521\u2013528 (2000)","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"40_CR7","unstructured":"Brin, S.: Near neighbor search in large metric spaces. In: VLDB. pp. 574\u2013584 (1995)"},{"key":"40_CR8","unstructured":"Chirikjian, G.S., Zhou, S.: Metrics on motion and deformation of solid models. J. Mech. Des. 120(2), 252\u2013261 (1998)"},{"key":"40_CR9","unstructured":"Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementation. MIT Press (June 2005)"},{"key":"40_CR10","doi-asserted-by":"crossref","unstructured":"Cohen, J.D., Lin, M.C., Manocha, D., Ponamgi, M.: I-COLLIDE: an interactive and exact collision detection system for large-scale environments. In: Symposium on Interactive 3D Graphics. pp. 1891\u201396, 218 (1995)","DOI":"10.1145\/199404.199437"},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"\u015eucan, I.A., Moll, M., Kavraki, L.E.: The Open Motion Planning Library. IEEE Robotics & Automation Magazine 19(4), 72\u201382 (2012)","DOI":"10.1109\/MRA.2012.2205651"},{"key":"40_CR12","unstructured":"Friedman, J.H., Bentley, J.L., Finkel, R.A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw. 3(3), 209\u2013226 (1977)"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Gammell, J.D., Srinivasa, S.S., Barfoot, T.D.: Informed RRT*: Optimal samplingbased path planning focused via direct sampling of an admissible ellipsoidal heuristic. In: IROS. pp. 2997\u20133004 (2014)","DOI":"10.1109\/IROS.2014.6942976"},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Hauser, K.: Lazy collision checking in asymptotically-optimal motion planning. In: ICRA. pp. 2951\u20132957 (2015)","DOI":"10.1109\/ICRA.2015.7139603"},{"key":"40_CR15","unstructured":"Hemmer, M., Kleinbort, M., Halperin, D.: Optimal randomized incremental construction for guaranteed logarithmic planar point location. Comput. Geom. 58,110\u2013123 (2016)"},{"key":"40_CR16","unstructured":"Hubbard, P.M.: Approximating polyhedra with spheres for time-critical collision detection. ACM Trans. Graph. 15(3), 179\u2013210 (1996)"},{"key":"40_CR17","doi-asserted-by":"crossref","unstructured":"Ichnowski, J., Alterovitz, R.: Fast nearest neighbor search in SE(3) for samplingbased motion planning. In: WAFR. pp. 197\u2013214 (2014)","DOI":"10.1007\/978-3-319-16595-0_12"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, chap. 39, pp. 877\u2013892. CRC Press LLC, Boca Raton, FL, 2nd edn. (2004)","DOI":"10.1201\/9781420035315.ch39"},{"key":"40_CR19","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: STOC. pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Janson, L., Schmerling, E., Clark, A.A., Pavone, M.: Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions. I. J. Robotic Res. 34(7), 883\u2013921 (2015)","DOI":"10.1177\/0278364915577958"},{"key":"40_CR21","doi-asserted-by":"crossref","unstructured":"Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. I. J. Robotic Res. 30(7), 846\u2013894 (2011)","DOI":"10.1177\/0278364911406761"},{"key":"40_CR22","doi-asserted-by":"crossref","unstructured":"Kleinbort, M., Salzman, O., Halperin, D.: Efficient high-quality motion planning by fast all-pairs r-nearest-neighbors. In: ICRA. pp. 2985\u20132990 (2015)","DOI":"10.1109\/ICRA.2015.7139608"},{"key":"40_CR23","unstructured":"Kleinbort, M., Salzman, O., Halperin, D.: Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning. CoRR abs\/1607.04800 (2016)"},{"key":"40_CR24","unstructured":"Larsen, E., Gottschalk, S., Lin, M.C., Manocha, D.: Fast proximity queries with swept sphere volumes. Tech. rep., Department of Computer Science, University of North Carolina (1999), TR99-018"},{"key":"40_CR25","doi-asserted-by":"crossref","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press (2006)","DOI":"10.1017\/CBO9780511546877"},{"key":"40_CR26","doi-asserted-by":"crossref","unstructured":"Lin, M.C., Manocha, D.: Collision and proximity queries. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, chap. 35, pp. 767\u2013786. CRC Press LLC, Boca Raton, FL, 2nd edn. (2004)","DOI":"10.1201\/9781420035315.ch35"},{"key":"40_CR27","unstructured":"Marichal, J.L., Dorff, M.: Derivative relationships between volume and surface area of compact regions in $$\\mathbb{R}^d$$. Rocky Mountain J. Math. 37(2), 551\u2013571 (2007)"},{"key":"40_CR28","unstructured":"Mazzola, G., Milmeister, G., Weissmann, J.: Comprehensive Mathematics for Computer Scientists 2, chap. 31, pp. 87\u201395. Springer, Berlin, Heidelberg (2005)"},{"key":"40_CR29","doi-asserted-by":"crossref","unstructured":"Pan, J., Chitta, S., Manocha, D.: FCL: A general purpose library for collision and proximity queries. In: ICRA. pp. 3859\u20133866 (2012)","DOI":"10.1109\/ICRA.2012.6225337"},{"key":"40_CR30","doi-asserted-by":"crossref","unstructured":"Plaku, E., Kavraki, L.E.: Quantitative analysis of nearest-neighbors search in high-dimensional sampling-based motion planning. In: WAFR. pp. 3\u201318 (2006)","DOI":"10.1007\/978-3-540-68405-3_1"},{"key":"40_CR31","doi-asserted-by":"crossref","unstructured":"Salzman, O., Halperin, D.: Asymptotically-optimal motion planning using lower bounds on cost. In: ICRA. pp. 4167\u20134172 (2015)","DOI":"10.1109\/ICRA.2015.7139773"},{"key":"40_CR32","unstructured":"Salzman, O., Halperin, D.: Asymptotically near-optimal RRT for fast, highquality, motion planning. IEEE Trans. Robotics 32(3), 473\u2013483 (2016)"},{"key":"40_CR33","unstructured":"Solovey, K., Salzman, O., Halperin, D.: New perspective on sampling-based motion planning via random geometric graphs. Robots Science and Systems (RSS) (2016)"},{"key":"40_CR34","unstructured":"Yershova, A., LaValle, S.M.: Improving motion-planning algorithms by efficient nearest-neighbor searching. IEEE Trans. Robotics 23(1), 151\u2013157 (2007)"}],"container-title":["Springer Proceedings in Advanced Robotics","Algorithmic Foundations of Robotics XII"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-43089-4_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T16:16:25Z","timestamp":1588781785000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-43089-4_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030430887","9783030430894"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-43089-4_40","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"value":"2511-1256","type":"print"},{"value":"2511-1264","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"7 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}