← 研踪 PaperTrailarXiv:2611.15320 · v1
Delaunay-Based Nearest Neighbor Search with Grid-Accelerated Queries and Parallel Construction
首次提交 2026-11-11 18:57
版本更新 2026-11-11 18:57
雷达观测 2026-11-13 11:11
摘要
Nearest-neighbor search is a fundamental primitive in computer graphics, with applications in distance field computation, surface reconstruction, and point cloud registration. In many graphics applications, data points lie on a surface manifold embedded in 3D space, whereas queries are distributed throughout the surrounding volume, a setting in which spatial partitioning structures such as k-d trees and grids can become inefficient. Dynamic-programming-based nearest-neighbor search (DP-NNS) offers an alternative: it traverses a successor DAG that records the history of incremental Delaunay construction and often outperforms spatial partitioning structures. However, its sequential construction is slow, and naive parallelization degrades query performance, limiting its practical adoption. We accelerate both queries and construction in DP-NNS. For queries, we introduce a grid-based initialization strategy that precomputes valid starting points on the successor DAG, shortening search paths while preserving exactness and enabling a twofold speedup. For construction, we analyze how parallel insertion affects query cost and develop a parallel algorithm that preserves logarithmic expected query cost under stated geometric assumptions. Our parallel construction algorithm achieves a 10x speedup over the sequential baseline while maintaining nearly the same query cost. We further reorder query points to improve cache locality. Extensive experiments demonstrate that our method outperforms widely used libraries in nearest-neighbor query performance.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-11 18:57 · 最新观测版本
Delaunay-Based Nearest Neighbor Search with Grid-Accelerated Queries and Parallel Construction
Nearest-neighbor search is a fundamental primitive in computer graphics, with applications in distance field computation, surface reconstruction, and point cloud registration. In many graphics applications, data points lie on a surface manifold embedded in 3D space, whereas queries are distributed throughout the surrounding volume, a setting in which spatial partitioning structures such as k-d trees and grids can become inefficient. Dynamic-programming-based nearest-neighbor search (DP-NNS) offers an alternative: it traverses a successor DAG that records the history of incremental Delaunay construction and often outperforms spatial partitioning structures. However, its sequential construction is slow, and naive parallelization degrades query performance, limiting its practical adoption. We accelerate both queries and construction in DP-NNS. For queries, we introduce a grid-based initialization strategy that precomputes valid starting points on the successor DAG, shortening search paths while preserving exactness and enabling a twofold speedup. For construction, we analyze how parallel insertion affects query cost and develop a parallel algorithm that preserves logarithmic expected query cost under stated geometric assumptions. Our parallel construction algorithm achieves a 10x speedup over the sequential baseline while maintaining nearly the same query cost. We further reorder query points to improve cache locality. Extensive experiments demonstrate that our method outperforms widely used libraries in nearest-neighbor query performance.
查看此版本解读 →查看此版本原文 ↗