{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T08:16:53Z","timestamp":1783066613266,"version":"3.54.6"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T00:00:00Z","timestamp":1783036800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U23A20312"],"award-info":[{"award-number":["U23A20312"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62272277"],"award-info":[{"award-number":["62272277"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62472257"],"award-info":[{"award-number":["62472257"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["ZR2025MS986"],"award-info":[{"award-number":["ZR2025MS986"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2026,7,3]]},"abstract":"\n k<\/jats:italic>\n -nearest neighbor (\n k<\/jats:italic>\n -NN) search is a fundamental primitive in geometry processing and computer graphics. While spatial partitioning structures such as\n kd<\/jats:italic>\n -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\n p<\/jats:italic>\n maintains a list of\n successors<\/jats:italic>\n that progressively refine its Voronoi cell. However, DP-NNS is restricted to single nearest neighbor (\n k<\/jats:italic>\n = 1) searches, precluding their adoption in applications that require local neighborhood statistics.\n <\/jats:p>\n \n In this paper, we generalize the DP-NNS framework to support arbitrary\n k<\/jats:italic>\n -NN queries for manifold-aligned data. Our approach is founded on the geometric observation that if\n \n p\n i<\/jats:sub>\n <\/jats:italic>\n is the nearest neighbor of a query\n q<\/jats:italic>\n in\n P<\/jats:italic>\n , then the second nearest neighbor of\n q<\/jats:italic>\n must reside either within the prefix set\n P<\/jats:italic>\n \n 1:\n i<\/jats:italic>\n -1\n <\/jats:sub>\n = [\n p<\/jats:italic>\n 1<\/jats:sub>\n , ...,\n p<\/jats:italic>\n i-1<\/jats:sub>\n } or within\n \n p\n i<\/jats:sub>\n <\/jats:italic>\n 's successor list. By recursively extending this principle, we introduce\n Manifold<\/jats:bold>\n k<\/jats:italic>\n -NN, a recursive algorithmic scheme that significantly outperforms conventional\n kd<\/jats:italic>\n -trees for manifold-aligned data. Our method achieves a 1\u00d7-10\u00d7 speedup in volume-to-surface query scenarios and inherently supports\n dynamic prefix<\/jats:italic>\n queries\u2014enabling\n k<\/jats:italic>\n -NN searches within any subset\n P<\/jats:italic>\n \n 1:\n m<\/jats:italic>\n <\/jats:sub>\n (\n m<\/jats:italic>\n \u2264\n n<\/jats:italic>\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.\n <\/jats:p>\n Source code is available at https:\/\/github.com\/sssomeone\/manifold-knn.<\/jats:p>","DOI":"10.1145\/3811271","type":"journal-article","created":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T07:05:51Z","timestamp":1783062351000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds"],"prefix":"10.1145","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2079-275X","authenticated-orcid":false,"given":"Pengfei","family":"Wang","sequence":"first","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7289-3557","authenticated-orcid":false,"given":"Qinghao","family":"Guo","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6389-1045","authenticated-orcid":false,"given":"Haisen","family":"Zhao","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8452-8723","authenticated-orcid":false,"given":"Shiqing","family":"Xin","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0835-3316","authenticated-orcid":false,"given":"Shuangmin","family":"Chen","sequence":"additional","affiliation":[{"name":"Qingdao University of Science and Technology, Qingdao, China"},{"name":"Shandong Key Laboratory of Deep Sea Equipment Intelligent Networking, Qingdao, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1231-3392","authenticated-orcid":false,"given":"Changhe","family":"Tu","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2284-3952","authenticated-orcid":false,"given":"Wenping","family":"Wang","sequence":"additional","affiliation":[{"name":"Texas A&M University, Texas, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/882370.882401"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2003.1175093"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777823"},{"key":"e_1_2_1_4_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Baorui Ma","year":"2021","unstructured":"Ma Baorui, Han Zhizhong, Liu Yu-Shen, and Zwicker Matthias. 2021. Neural-Pull: Learning Signed Distance Functions from Point Clouds by Learning to Pull Space onto Surfaces. In International Conference on Machine Learning (ICML)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98741"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.121791"},{"key":"e_1_2_1_8_1","unstructured":"Jose Luis Blanco and Pranjal Kumar Rai. 2014. nanoflann: a C++ header-only fork of FLANN a library for Nearest Neighbor (NN) with KD-trees. https:\/\/github.com\/jlblancoc\/nanoflann."},{"key":"e_1_2_1_9_1","unstructured":"Boost. 2015. Boost C++ Libraries. http:\/\/www.boost.org\/. Last accessed 2015-06-30."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR52688.2022.00620"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.162"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58558-7_7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_14_1","unstructured":"Susan Hert and Michael Seel. 2024. dD Convex Hulls and Delaunay Triangulations. In CGAL User and Reference Manual (5.6.1 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.6.1\/Manual\/packages.html#PkgConvexHullD"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/142920.134011"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/133994.134011"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-012-9321-0"},{"key":"e_1_2_1_18_1","volume-title":"ABC: A Big CAD Model Dataset For Geometric Deep Learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).","author":"Koch Sebastian","year":"2019","unstructured":"Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Marc Alexa, Denis Zorin, and Daniele Panozzo. 2019. ABC: A Big CAD Model Dataset For Geometric Deep Learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316762"},{"key":"e_1_2_1_20_1","volume-title":"Afaque R Memon, et al.","author":"Li Jianning","year":"2023","unstructured":"Jianning Li, Antonio Pepe, Christina Gsaxner, Gijs Luijten, Yuan Jin, Narmada Ambigapathy, Enrico Nasca, Naida Solak, Gian Marco Melito, Afaque R Memon, et al. 2023. MedShapeNet-A Large-Scale Dataset of 3D Medical Shapes for Computer Vision. arXiv preprint arXiv:2308.16139 (2023)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777840"},{"key":"e_1_2_1_22_1","volume-title":"The ArborX Library: Version 2.0. ACM Trans. Math. Software 51","author":"Prokopenko Andrey","year":"2025","unstructured":"Andrey Prokopenko, Daniel Arndt, Damien Lebrun-Grandi\u00e9, and Bruno Turcksin. 2025. The ArborX Library: Version 2.0. ACM Trans. Math. Software 51 (2025), 1\u201310. https:\/\/api.semanticscholar.org\/CorpusID:280401698"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980567"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/cav.1775"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1908.133.97"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2025.3610211"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3721238.3730671"},{"key":"e_1_2_1_28_1","volume-title":"Point-NeRF: Point-based Neural Radiance Fields. 2022 IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Xu Qiangeng","year":"2022","unstructured":"Qiangeng Xu, Zexiang Xu, Julien Philip, Sai Bi, Zhixin Shu, Kalyan Sunkavalli, and Ulrich Neumann. 2022c. Point-NeRF: Point-based Neural Radiance Fields. 2022 IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (2022), 5428\u20135438. https:\/\/api.semanticscholar.org\/CorpusID:246210101"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555443"},{"key":"e_1_2_1_30_1","volume-title":"Fast-lio2: Fast direct lidar-inertial odometry","author":"Xu Wei","year":"2022","unstructured":"Wei Xu, Yixi Cai, Dongjiao He, Jiarong Lin, and Fu Zhang. 2022a. Fast-lio2: Fast direct lidar-inertial odometry. IEEE Transactions on Robotics (2022)."},{"key":"e_1_2_1_31_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).","journal-title":"A Dataset of"},{"key":"e_1_2_1_32_1","volume-title":"Open3D: A Modern Library for 3D Data Processing. arXiv:1801.09847","author":"Zhou Qian-Yi","year":"2018","unstructured":"Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun. 2018. Open3D: A Modern Library for 3D Data Processing. arXiv:1801.09847 (2018)."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T07:30:13Z","timestamp":1783063813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3811271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,3]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,7,3]]}},"alternative-id":["10.1145\/3811271"],"URL":"https:\/\/doi.org\/10.1145\/3811271","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,3]]},"assertion":[{"value":"2025-12-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-07-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}