{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:26:46Z","timestamp":1771025206433,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Vision and Applications"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Point set registration algorithms such as Iterative Closest Point (ICP) are commonly utilized in time-constrained environments like robotics. Finding the nearest neighbor of a point in a <jats:italic>reference<\/jats:italic> 3D point set is a common operation in ICP and frequently consumes at least 90% of the computation time. We introduce a novel approach to performing the distance-based nearest neighbor step based on Delaunay triangulation. This greedy algorithm finds the nearest neighbor of a query point by traversing the edges of the Delaunay triangulation created from a <jats:italic>reference<\/jats:italic> 3D point set. Our work integrates the Delaunay traversal into the correspondences search of ICP and exploits the iterative aspect of ICP by caching previous correspondences to expedite each iteration. An algorithmic analysis and comparison is conducted showing an order of magnitude speedup for both serial and vector processor implementation.<\/jats:p>","DOI":"10.1007\/s00138-022-01279-w","type":"journal-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T15:02:51Z","timestamp":1644937371000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Delaunay walk for fast nearest neighbor: accelerating correspondence matching for ICP"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5154-7725","authenticated-orcid":false,"given":"James D.","family":"Anderson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan M.","family":"Raettig","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Josh","family":"Larson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Scott L.","family":"Nykl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clark N.","family":"Taylor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Wischgoll","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,15]]},"reference":[{"key":"1279_CR1","unstructured":"3rd gen ryzen$$^{{\\rm TM}}$$ threadripper$$^{{\\rm TM}}$$ 3970x | desktop processor | amd. https:\/\/www.amd.com\/en\/products\/cpu\/amd-ryzen-threadripper-3970x. Accessed on 01\/11\/2021"},{"key":"1279_CR2","unstructured":"Geforce rtx 3080 graphics card | nvidia. https:\/\/www.nvidia.com\/en-us\/geforce\/graphics-cards\/30-series\/rtx-3080\/. Accessed on 01\/11\/2021"},{"key":"1279_CR3","unstructured":"Tracker documentation - tracker 3.9 documentation - vicon documentation. https:\/\/docs.vicon.com\/display\/Tracker39. Accessed on 01\/13\/2021"},{"key":"1279_CR4","doi-asserted-by":"publisher","unstructured":"Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discret. Comput. Geom. (1999). https:\/\/doi.org\/10.1007\/PL00009475","DOI":"10.1007\/PL00009475"},{"key":"1279_CR5","unstructured":"Anderson, J.: Delaunay walk for fast nearest neighbor matching. https:\/\/youtu.be\/wI6MiRx-5Ik (2021). Accessed on 14\/04\/2021"},{"key":"1279_CR6","doi-asserted-by":"publisher","unstructured":"Anderson, S.J., Karumanchi, S.B., Iagnemma, K.: Constraint-based planning and control for safe, semi-autonomous operation of vehicles. In: IEEE Intelligent Vehicles Symposium Proceeding (2012). https:\/\/doi.org\/10.1109\/IVS.2012.6232153","DOI":"10.1109\/IVS.2012.6232153"},{"issue":"4","key":"1279_CR7","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/235815.235821","volume":"22","author":"CB Barber","year":"1996","unstructured":"Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22(4), 469\u2013483 (1996). https:\/\/doi.org\/10.1145\/235815.235821","journal-title":"ACM Trans. Math. Softw."},{"key":"1279_CR8","first-page":"2015","volume":"1","author":"B Bellekens","year":"2015","unstructured":"Bellekens, B., Spruyt, V., Berkvens, R., Penne, R., Weyn, M.: A benchmark survey of rigid 3d point cloud registration algorithms. Int. J. Adv. Intell. Syst. 1, 2015 (2015)","journal-title":"Int. J. Adv. Intell. Syst."},{"key":"1279_CR9","doi-asserted-by":"publisher","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM (1975). https:\/\/doi.org\/10.1145\/361002.361007","DOI":"10.1145\/361002.361007"},{"key":"1279_CR10","doi-asserted-by":"publisher","unstructured":"Besl, P.J., McKay, N.D.: A method for registration of 3-D shapes. IEEE Trans. Pattern Anal. Mach. Intell. (1992). https:\/\/doi.org\/10.1109\/34.121791","DOI":"10.1109\/34.121791"},{"key":"1279_CR11","doi-asserted-by":"publisher","unstructured":"Birn, M., Holtgrewe, M., Sanders, P., Singler, J.: Simple and fast nearest neighbor search. In: 2010 Proceedings of the 12th Workshop on Algorithm Engineering and Experiments. ALENEX 2010 (2010). https:\/\/doi.org\/10.1137\/1.9781611972900.5","DOI":"10.1137\/1.9781611972900.5"},{"key":"1279_CR12","volume-title":"Delaunay Triangulation Based Surface Reconstruction: Ideas and Algorithms","author":"F Cazals","year":"2004","unstructured":"Cazals, F., Giesen, J.: Delaunay Triangulation Based Surface Reconstruction: Ideas and Algorithms. INRIA Rapp, Rech (2004)"},{"key":"1279_CR13","doi-asserted-by":"publisher","unstructured":"Chen, Y., Medioni, G.: Object modeling by registration of multiple range images. In: Proceedings of the IEEE International Conference on Robotics and Automation (1991). https:\/\/doi.org\/10.1109\/robot.1991.132043","DOI":"10.1109\/robot.1991.132043"},{"key":"1279_CR14","doi-asserted-by":"publisher","unstructured":"Cover, T.M., Hart, P.E.: Nearest Neighbor Pattern Classification. IEEE Trans. Inf. Theory (1967). https:\/\/doi.org\/10.1109\/TIT.1967.1053964","DOI":"10.1109\/TIT.1967.1053964"},{"key":"1279_CR15","unstructured":"Delaunay, B.: Sur la sph\u00e8re du vide. Bull. l\u2019Acad\u00e9mie des Sci. l\u2019URSS (1934)"},{"key":"1279_CR16","doi-asserted-by":"publisher","unstructured":"Drost, B.H., Ilic, S.: Almost constant-time 3D nearest-neighbor lookup using implicit octrees. Mach. Vis. Appl. (2018). https:\/\/doi.org\/10.1007\/s00138-017-0889-4","DOI":"10.1007\/s00138-017-0889-4"},{"key":"1279_CR17","doi-asserted-by":"publisher","unstructured":"Friedman, J.H., Bentley, J.L., Finkel, R.A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw. (1977). https:\/\/doi.org\/10.1145\/355744.355745","DOI":"10.1145\/355744.355745"},{"key":"1279_CR18","doi-asserted-by":"publisher","unstructured":"Greenspan, M., Yurick, M.: Approximate k-d tree search for efficient ICP. In: Proceedings of the International Conference on 3D Digital Imaging and Modeling 3DIM (2003). https:\/\/doi.org\/10.1109\/IM.2003.1240280","DOI":"10.1109\/IM.2003.1240280"},{"issue":"2","key":"1279_CR19","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/971697.602266","volume":"14","author":"A Guttman","year":"1984","unstructured":"Guttman, A.: R-trees: a dynamic index structure for spatial searching. ACM SIGMOD Rec. 14(2), 47\u201357 (1984). https:\/\/doi.org\/10.1145\/971697.602266","journal-title":"ACM SIGMOD Rec."},{"key":"1279_CR20","volume-title":"Learning OpenCV 3: computer vision in C++ with the OpenCV library","author":"A Kaehler","year":"2016","unstructured":"Kaehler, A., Bradski, G.: Learning OpenCV 3: computer vision in C++ with the OpenCV library. O\u2019Reilly Media, Newton (2016)"},{"key":"1279_CR21","doi-asserted-by":"publisher","unstructured":"Labatut, P., Pons, J.P., Keriven, R.: Robust and efficient surface reconstruction from range data. Comput. Graph. Forum (2009). https:\/\/doi.org\/10.1111\/j.1467-8659.2009.01530.x","DOI":"10.1111\/j.1467-8659.2009.01530.x"},{"issue":"3","key":"1279_CR22","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF00977785","volume":"9","author":"DT Lee","year":"1980","unstructured":"Lee, D.T., Schachter, B.J.: Two algorithms for constructing a Delaunay triangulation. Int. J. Comput. Inf. Sci. 9(3), 219\u2013242 (1980)","journal-title":"Int. J. Comput. Inf. Sci."},{"key":"1279_CR23","doi-asserted-by":"publisher","unstructured":"Li, X.Y., Calinescu, G., Wan, P.J.: Distributed construction of a planar spanner and routing for ad hoc wireless networks. In: Proceedings of the IEEE INFOCOM (2002). https:\/\/doi.org\/10.1109\/INFCOM.2002.1019377","DOI":"10.1109\/INFCOM.2002.1019377"},{"key":"1279_CR24","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.cma.2012.05.009","volume":"237\u2013240","author":"SH Lo","year":"2012","unstructured":"Lo, S.H.: Parallel Delaunay triangulation in three dimensions. Comput. Methods Appl. Mech. Eng. 237\u2013240, 88\u2013106 (2012). https:\/\/doi.org\/10.1016\/j.cma.2012.05.009","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"1279_CR25","volume-title":"Linear Least-squares Optimization for Point-to-plane ICP Surface Registration","author":"K Low","year":"2004","unstructured":"Low, K.: Linear Least-squares Optimization for Point-to-plane ICP Surface Registration. Univ. North Carolina, Chapel Hill (2004)"},{"key":"1279_CR26","unstructured":"Marden, S., Guivant, J.: Improving the performance of ICP for real-time applications using an approximate nearest neighbour search. In: Australasian Conference on Robotics and Automation ACRA (2012)"},{"key":"1279_CR27","unstructured":"Meagher, D.J.: Octree encoding: A new technique for the representation, manipulation and display of arbitrary 3-d objects by computer. Electrical and Systems Engineering Department Rensseiaer Polytechnic (1980)"},{"key":"1279_CR28","unstructured":"Muja, M., Lowe, D.G.: Fast approximate nearest neighbors with automatic algorithm configuration. In: VISAPP 2009\u2014Proceedings of the 4th International Conference on Computer Vision Theory and Applications (2009)"},{"issue":"11","key":"1279_CR29","doi-asserted-by":"publisher","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","volume":"36","author":"M Muja","year":"2014","unstructured":"Muja, M., Lowe, D.G.: Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans. Pattern Anal. Mach. Intell. 36(11), 2227\u20132240 (2014). https:\/\/doi.org\/10.1109\/TPAMI.2014.2321376","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"1279_CR30","doi-asserted-by":"publisher","unstructured":"Mulchrone, K.F.: Application of Delaunay triangulation to the nearest neighbour method of strain analysis. J. Struct. Geol. (2003). https:\/\/doi.org\/10.1016\/S0191-8141(02)00067-6","DOI":"10.1016\/S0191-8141(02)00067-6"},{"key":"1279_CR31","doi-asserted-by":"publisher","unstructured":"Myronenko, A., Song, X.: Point-set registration: coherent point drift. IEEE Trans. Pattern Anal. Mach. Intell. 32(12), 2262\u20132275 (2010). https:\/\/doi.org\/10.1109\/TPAMI.2010.46. arXiv:0905.2635","DOI":"10.1109\/TPAMI.2010.46"},{"key":"1279_CR32","doi-asserted-by":"publisher","unstructured":"N\u00fcchter, A., Lingemann, K., Hertzberg, J.: Cached k-d tree search for ICP algorithms. In: 3DIM 2007\u2014Proceedings of the International Conference on 3D Digital Imaging and Modeling (2007). https:\/\/doi.org\/10.1109\/3DIM.2007.15","DOI":"10.1109\/3DIM.2007.15"},{"key":"1279_CR33","unstructured":"NVIDIA: CUDA Toolkit Documentation v11.2.76. https:\/\/docs.nvidia.com\/cuda\/"},{"key":"1279_CR34","doi-asserted-by":"publisher","unstructured":"Pan, J., Manocha, D.: Fast GPU-based locality sensitive hashing for k-nearest neighbor computation. In: GIS Proceedings of the ACM International Symposium on Geographic Information Systems (2011). https:\/\/doi.org\/10.1145\/2093973.2094002","DOI":"10.1145\/2093973.2094002"},{"key":"1279_CR35","doi-asserted-by":"publisher","unstructured":"Pomerleau, F., Colas, F., Siegwart, R.: A review of point cloud registration algorithms for mobile robotics. Found. Trends Robot. (2015). https:\/\/doi.org\/10.1561\/2300000035","DOI":"10.1561\/2300000035"},{"key":"1279_CR36","unstructured":"Qiu, T., Li, Y.: Nonparametric Nearest Neighbor Descent Clustering based on Delaunay Triangulation. arXiv Preprint arXiv:1502.04837 (2015)"},{"key":"1279_CR37","unstructured":"Raettig, R.M., Anderson, J.D., Nykl, S.L., Merkle, L.D.: Accelerated point set registration method (2020)"},{"key":"1279_CR38","doi-asserted-by":"publisher","unstructured":"Segal, A., H\u00e4hnel, D., Thrun, S.: Generalized-icp (2009). https:\/\/doi.org\/10.15607\/RSS.2009.V.021","DOI":"10.15607\/RSS.2009.V.021"},{"key":"1279_CR39","doi-asserted-by":"publisher","unstructured":"Stepanov, A., Smith, J.M.G.: Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms. Eur. J. Oper. Res. (2012). https:\/\/doi.org\/10.1016\/j.ejor.2011.11.031","DOI":"10.1016\/j.ejor.2011.11.031"},{"key":"1279_CR40","doi-asserted-by":"publisher","unstructured":"Weinberger, K.Q., Saul, L.K.: Distance metric learning for large margin nearest neighbor classification. J. Mach. Learn. Res. (2009). https:\/\/doi.org\/10.1145\/1577069.1577078","DOI":"10.1145\/1577069.1577078"},{"key":"1279_CR41","unstructured":"Zhou, Q.Y., Park, J., Koltun, V.: Open3D: A modern library for 3D data processing. arXiv:1801.09847 (2018)"},{"issue":"5","key":"1279_CR42","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.3390\/s19051191","volume":"19","author":"H Zhu","year":"2019","unstructured":"Zhu, H., Guo, B., Zou, K., Li, Y., Yuen, K.V., Mihaylova, L., Leung, H.: A review of point set registration: From pairwise registration to groupwise registration. Sensors 19(5), 1191 (2019)","journal-title":"Sensors"}],"container-title":["Machine Vision and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00138-022-01279-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00138-022-01279-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00138-022-01279-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,12]],"date-time":"2022-03-12T09:07:06Z","timestamp":1647076026000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00138-022-01279-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,15]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1279"],"URL":"https:\/\/doi.org\/10.1007\/s00138-022-01279-w","relation":{},"ISSN":["0932-8092","1432-1769"],"issn-type":[{"value":"0932-8092","type":"print"},{"value":"1432-1769","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,15]]},"assertion":[{"value":"14 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"31"}}