.png){kind=icon}
.png){kind=icon}
Return
Efficient Nearest Neighbor Search Using Dynamic Programming
.png){kind=icon}
PRE
AI
DOI：10.1109/TPAMI.2025.3610211.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a collection of points in <inline-formula><tex-math notation="LaTeX">$\mathbb {R}^{3}$</tex-math></inline-formula>, KD-Tree and R-Tree are well-known nearest neighbor search (NNS) algorithms that rely on spatial partitioning and indexing techniques. However, when the query point is far from the data points or the data points inherently represent a 2-manifold surface, their query performance may degrade. To address this, we propose a novel dynamic programming technique that precomputes a Directed Acyclic Graph (DAG) to encode the proximity structure between data points. More specifically, the DAG captures how the proximity structure evolves during the incremental construction of the Voronoi diagram of the data points. Experimental results demonstrate that our method achieves a speed increase of 1-10x. Furthermore, our algorithm demonstrates significant practical value in diverse applications. We validated its effectiveness through extensive testing in four key applications: Point-to-Mesh Distance Queries, Iterative Closest Point (ICP) Registration, Density Peak Clustering, and Point-to-Segments Distance Queries. A particularly notable feature of our approach is its unique ability to efficiently identify the nearest neighbor among the first <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> points in the point cloud, a capability that enables substantial acceleration in low-dimensional applications like Density Peak Clustering. As a natural extension of our incremental construction process, our method can also be readily adapted for farthest-point sampling tasks. These experimental results across multiple domains underscore the broad applicability and practical importance of our approach.
Keywords:
Nearest neighbor search
delaunay triangulation
voronoi diagram
farthest point sampling
density peak clustering
Journal
IF:
18.6
Papers:
831
Citations:
9.8W
View more organizations