Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds
ACM Transactions on Graphics · 03.07.2026 · 45 (4) · 1-12
DOI: 10.1145/3811271 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Graphics, online erschienen am 03.07.2026. Verfasst von Pengfei Wang und 6 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
k -nearest neighbor ( k -NN) search is a fundamental primitive in geometry processing and computer graphics. While spatial partitioning structures such as kd -trees are standard, they are often manifold-blind, failing to exploit the intrinsic low-dimensional structure of points sampled from 2-manifolds. Recent advances in dynamic programming-based nearest neighbor search (DP-NNS) leverage incrementally constructed Voronoi diagrams to accelerate queries, where each site p maintains a list of successors that progressively refine its Voronoi cell. However, DP-NNS is restricted to single nearest neighbor ( k = 1) searches, precluding their adoption in applications that require local neighborhood statistics. In this paper, we generalize the DP-NNS framework to support arbitrary k -NN queries for manifold-aligned data. Our approach is founded on the geometric observation that if p i is the nearest neighbor of a query q in P , then the second nearest neighbor of q must reside either within the prefix set P 1: i -1 = [ p 1 , ..., p i-1 } or within p i 's successor list. By recursively extending this principle, we introduce Manifold k -NN, a recursive algorithmic scheme that significantly outperforms conventional kd -trees for manifold-aligned data. Our method achieves a 1×-10× speedup in volume-to-surface query scenarios and inherently supports dynamic prefix queries—enabling k -NN searches within any subset P 1: m ( m ≤ n ) with zero overhead. Furthermore, we extend the framework to support point deletion via local Delaunay updates, providing a complete suite of dynamic operations for point set modification. Comprehensive experiments on diverse geometric datasets demonstrate the efficiency and broad applicability of our approach for modern graphics pipelines. Source code is available at https://github.com/sssomeone/manifold-knn.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Wang, P., Guo, Q., Zhao, H., Xin, S., Chen, S., Tu, C., & Wang, W. (2026). Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds. ACM Transactions on Graphics, 45(4), 1-12. https://doi.org/10.1145/3811271
Vancouver
Wang P, Guo Q, Zhao H, Xin S, Chen S, Tu C, et al. Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds. ACM Transactions on Graphics. 2026;45(4):1-12. doi:10.1145/3811271
BibTeX
@article{Wang2026,
author = {Wang, Pengfei and Guo, Qinghao and Zhao, Haisen and Xin, Shiqing and Chen, Shuangmin and Tu, Changhe and Wang, Wenping},
title = {Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds},
journal = {ACM Transactions on Graphics},
year = {2026},
volume = {45},
number = {4},
pages = {1--12},
doi = {10.1145/3811271}
}
EUVIMED