{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:18:47Z","timestamp":1763468327219,"version":"3.45.0"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,7,24]],"date-time":"2017-07-24T00:00:00Z","timestamp":1500854400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-0915665"],"award-info":[{"award-number":["IIS-0915665"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,7,24]]},"DOI":"10.1145\/2897826.2927310","type":"proceedings-article","created":{"date-parts":[[2016,7,12]],"date-time":"2016-07-12T08:11:05Z","timestamp":1468311065000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Geometric and discrete path planning for interactive virtual worlds"],"prefix":"10.1145","author":[{"given":"Marcelo","family":"Kallmann","sequence":"first","affiliation":[{"name":"University of California Merced"}]},{"given":"Mubbasir","family":"Kapadia","sequence":"additional","affiliation":[{"name":"Rutgers University"}]}],"member":"320","published-online":{"date-parts":[[2016,7,24]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336206"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566606"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2822013.2822043"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2008.921540"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2668064.2668092"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.58"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323261"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2009. Introduction to Algorithms Third Edition 3rd ed. The MIT Press.","DOI":"10.5555\/1614191"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1597538.1597687"},{"volume-title":"Proceedings of the 5th Workshop Algorithm Engineering and Experiments, 37--44","author":"Devillers O.","key":"e_1_3_2_2_12_1","unstructured":"Devillers, O., and Pion, S. 2003. Efficient exact geometric predicates for delaunay triangulations. In Proceedings of the 5th Workshop Algorithm Engineering and Experiments, 37--44."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"volume-title":"Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA.","author":"Garcia F.","key":"e_1_3_2_2_14_1","unstructured":"Garcia, F., Kapadia, M., and Badler, N. I. 2014. Gpu-based dynamic search on adaptive resolution grids. In Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509263"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Gochev K. Cohen B. J. Butzke J. Safonova A. and Likhachev M. 2011. Path planning with adaptive dimensionality. In SOCS.","DOI":"10.1109\/ICRA.2012.6225228"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90010-8"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","unstructured":"Hjelle O. and D\u00e6hlen M. 2006. Triangulations and Applications (Mathematics and Visualization). Springer-Verlag New York Inc. Secaucus NJ USA.","DOI":"10.5555\/1214284"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336226"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2446494"},{"volume-title":"Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA '14","author":"Huang T.","key":"e_1_3_2_2_23_1","unstructured":"Huang, T., Kapadia, M., Badler, N. I., and Kallmann, M. 2014. Path planning for coherent and persistent groups. In Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA '14."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25090-3_30"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2614028.2615399"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Kallmann M. and Kapadia M. 2016. Geometric and Discrete Path Planning for Interactive Virtual Worlds. Morgan and Claypool Publishers.","DOI":"10.1007\/978-3-031-02588-4"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1948395.1948426"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1921427.1921451"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2580947"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Kapadia M. and Badler N. I. 2013. Navigation and steering for autonomous virtual humans. Wiley Interdisciplinary Reviews: Cognitive Science.","DOI":"10.1002\/wcs.1223"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1507149.1507185"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2011.68"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-011-0669-5"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485895.2485909"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2522628.2522654"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.251"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2856400.2856404"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/777092.777167"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566605"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2004.00782.x"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01405.x"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140304"},{"key":"e_1_3_2_2_43_1","unstructured":"Likhachev M. Gordon G. J. and Thrun S. 2003. ARA*: Anytime A* with Provable Bounds on Sub-Optimality. In NIPS."},{"key":"e_1_3_2_2_44_1","unstructured":"Likhachev M. Ferguson D. I. Gordon G. J. Stentz A. and Thrun S. 2005. Anytime Dynamic A*: An Anytime Replanning Algorithm. In ICAPS 262--271."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.466615"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2421731.2421751"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.149"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2822013.2822044"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530888"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161156"},{"volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, IEEE, IROS '13","author":"Mubbasir Kapadia","key":"e_1_3_2_2_52_1","unstructured":"Mubbasir Kapadia, Francisco Garcia, C. D. B., and Badler, N. I. 2013. Dynamic search on the gpu. In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, IEEE, IROS '13."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1624562.1624607"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2522628.2522900"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2013.03.004"},{"key":"e_1_3_2_2_56_1","unstructured":"Recast 2014. Recast navigation mesh. https:\/\/github.com\/memononen\/recastnavigation."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/645908.673287"},{"key":"e_1_3_2_2_58_1","first-page":"3","article-title":"Adaptive precision floating-point arithmetic and fast robust geometric predicates","volume":"18","author":"Shewchuk J. R.","year":"1997","unstructured":"Shewchuk, J. R. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (Oct.), 305--363.","journal-title":"Discrete & Computational Geometry"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2522628.2522629"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448196.2448198"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1002\/cav.403"},{"key":"e_1_3_2_2_62_1","unstructured":"The CGAL Project. 2014. CGAL User and Reference Manual 4.4 ed. CGAL Editorial Board. http:\/\/doc.cgal.org\/4.4\/Manual\/packages.html."},{"key":"e_1_3_2_2_63_1","unstructured":"Tripath Toolkit 2010. Triangulation and path planning toolkit. http:\/\/graphics.ucmerced.edu\/software\/tripath\/."},{"volume-title":"In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), 3526--3532","author":"van Toll W. G., IV, A. F. C.","key":"e_1_3_2_2_64_1","unstructured":"van Toll, W. G., IV, A. F. C., and Geraerts, R. 2011. Navigation meshes for realistic multi-layered environments. In In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), 3526--3532."},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1002\/cav.1468"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.11.007"},{"key":"e_1_3_2_2_67_1","doi-asserted-by":"publisher","unstructured":"Xiao J. Zhuang Y. Yang T. and Wu F. 2006. An efficient keyframe extraction from motion capture data. In Advances in Computer Graphics vol. 4035 of LNCS. Springer Berlin Heidelberg 494--501. 10.1007\/11784203_44","DOI":"10.1007\/11784203_44"}],"event":{"name":"SIGGRAPH '16: Special Interest Group on Computer Graphics and Interactive Techniques Conference","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques"],"location":"Anaheim California","acronym":"SIGGRAPH '16"},"container-title":["ACM SIGGRAPH 2016 Courses"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897826.2927310","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897826.2927310","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897826.2927310","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:25:15Z","timestamp":1763457915000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897826.2927310"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,24]]},"references-count":67,"alternative-id":["10.1145\/2897826.2927310","10.1145\/2897826"],"URL":"https:\/\/doi.org\/10.1145\/2897826.2927310","relation":{},"subject":[],"published":{"date-parts":[[2016,7,24]]},"assertion":[{"value":"2016-07-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}