Physical Sciences and Mathematics Commons^™

Delaunay Walk For Fast Nearest Neighbor: Accelerating Correspondence Matching For Icp, James D. Anderson, Ryan M. Raettig, Josh Larson, Scott L. Nykl, Clark N. Taylor, Thomas Wischgoll

Computer Science and Engineering Faculty Publications

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 reference 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 reference 3D point set. Our work integrates the Delaunay traversal into the correspondences search of …