arxiv: 2605.02224 · v1 · submitted 2026-05-04 · 💻 cs.CG · cs.GR

Recognition: unknown

Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds

Changhe Tu, Haisen Zhao, Pengfei Wang, Qinghao Guo, Shiqing Xin, Shuangmin Chen, Wenping Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-08 01:50 UTC · model grok-4.3

classification 💻 cs.CG cs.GR

keywords k-nearest neighborsmanifold point cloudsVoronoi diagramssuccessor listsdynamic queriesgeometry processingDelaunay updates

0 comments

The pith

A recursive extension of Voronoi successor lists finds arbitrary k-nearest neighbors on manifold point clouds faster than kd-trees and supports dynamic prefixes and deletions at zero overhead.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper generalizes dynamic programming nearest-neighbor search to handle any k by using an observation about where the next closest point must lie. Each point maintains a successor list that refines its Voronoi cell as more points are added; the claim is that the second-nearest neighbor to any query is always either among the points added before the first neighbor or inside that first neighbor's successor list. This rule is applied recursively to locate the full k-set without examining the entire cloud. The approach matters because graphics pipelines often need local neighborhoods on surfaces sampled from 2-manifolds, and standard spatial trees ignore the intrinsic low-dimensional structure. If the rule holds, queries become substantially faster while also allowing searches inside any initial segment of the point list and supporting point removal through local updates.

Core claim

The central discovery is that the geometric property used for single nearest-neighbor search extends directly to arbitrary k: once the nearest neighbor p_i of a query q is known, the second nearest must reside either in the prefix set of points added before p_i or inside p_i's successor list, and the same property recurses for each subsequent neighbor. This yields a simple recursive algorithm that traverses only the relevant successor chains rather than the full point set.

What carries the argument

The recursive algorithmic scheme that locates each successive neighbor by checking only the prefix before the current nearest neighbor and the successor list of that neighbor.

If this is right

Volume-to-surface k-NN queries run between 1 and 10 times faster than kd-trees on manifold-aligned data.
k-NN searches inside any prefix subset P_{1:m} incur no extra cost beyond the query itself.
Point deletions are handled by local Delaunay updates that maintain the successor lists.
The same data structure supports both static and fully dynamic point-set operations in graphics pipelines.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The prefix-query property could simplify algorithms that process points in streaming or level-of-detail order.
If the successor-list construction can be adapted to non-manifold but low-dimensional samples, similar speedups might appear in other domains.
The local-update rule for deletions suggests the structure could be maintained under small insertions as well, though that is not demonstrated.

Load-bearing premise

The second nearest neighbor of any query always lies either in the points added before the first nearest neighbor or inside that first neighbor's successor list, and the property holds recursively for every higher rank up to k.

What would settle it

A single query point on a manifold point cloud where the second nearest neighbor lies outside both the prefix up to the first nearest neighbor and that neighbor's successor list would falsify the recursive rule.

Figures

Figures reproduced from arXiv: 2605.02224 by Changhe Tu, Haisen Zhao, Pengfei Wang, Qinghao Guo, Shiqing Xin, Shuangmin Chen, Wenping Wang.

**Figure 1.** Figure 1: Performance comparison in a volume-to-surface query scenario. For a dataset of 106 points sampled from a manifold surface (Earth) and 106 query points distributed within its 2× axis-aligned bounding box (AABB), retrieving 𝑘 = 20 neighbors exposes the inherent limitations of traditional structures. Standard volumetric indices, such as Octrees and 𝑘𝑑-trees, suffer from poor pruning and excessive node traver… view at source ↗

**Figure 2.** Figure 2: Core observation: a newly inserted point can only change the nearest view at source ↗

**Figure 3.** Figure 3: Illustration of the recursive search space partitioning for view at source ↗

**Figure 4.** Figure 4: Voronoi adjacency evolution following site deletion. view at source ↗

**Figure 5.** Figure 5: Visualization of representative point cloud models used in experi view at source ↗

**Figure 6.** Figure 6: Query time comparison across MedShapeNet, Thingi10K, and ABC view at source ↗

**Figure 7.** Figure 7: Preprocessing time comparison across MedShapeNet, Thingi10K and ABC datasets (from left to right). Dashed line indicates equal performance (ratio view at source ↗

**Figure 8.** Figure 8: Point deletion performance across different point cloud sizes. For view at source ↗

**Figure 9.** Figure 9: Performance comparison under dynamic scenarios. Target points lie view at source ↗

**Figure 12.** Figure 12: Query time comparison on uniform point clouds with varying numbers of target points. All query points were generated within the exact same spatial bounds as the target points. Our method achieves query performance comparable to R∗ -tree, KD-tree and ArborX while outperforming other baseline methods. 0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 Query Time ( s) Ours KD Tree R* Tree BD Tree ArborX 2D 3D 4D 5D 6D 7D … view at source ↗

**Figure 10.** Figure 10: Performance comparison under dynamic scenarios. Both target view at source ↗

**Figure 13.** Figure 13: Query time comparison across dimensions for uniform distribution view at source ↗

**Figure 11.** Figure 11: Query Time Performance Comparison Across Manifold Violation view at source ↗

read the original abstract

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, \dots, 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\times--10\times speedup in volume-to-surface query scenarios and inherently supports dynamic prefix queries -- enabling k-NN searches within any subset P_{1:m} (m \leq 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends DP-NNS successor lists to k-NN via recursion plus prefix and delete support, but the candidate-set completeness for arbitrary k is the part that needs checking.

read the letter

The main thing here is a recursive generalization of the DP-NNS successor-list idea so it works for k greater than 1 on manifold point clouds, along with zero-overhead prefix queries and local Delaunay updates for deletions. That combination is new relative to the cited prior work, which stopped at single nearest neighbors. They also report 1-10x speedups versus kd-trees in volume-to-surface cases and ship the code, which is useful for anyone who wants to plug it into a pipeline right away. The geometric observation is stated plainly and the dynamic features follow directly from the same structure, so the engineering side looks solid. The soft spot is exactly the one the stress-test flags: the recursion assumes that every subsequent neighbor will always land inside the prefix or the successor lists generated from the initial Voronoi construction. If the fixed ordering or the adjacency relations miss a direction on a given manifold, the candidate pool could be incomplete and the reported k-NN could be wrong rather than just slower. The abstract presents the property as holding, but without an explicit inductive argument or counter-example checks for k>2 it is hard to judge how often that actually happens in practice. Experiments are run on diverse geometric sets and the speedups look plausible, yet the lack of error bars and full baseline code in the abstract leaves room for tuning questions. This is for computational geometry and graphics people who already work with surface-sampled points and need faster local neighborhoods plus dynamic updates. It is worth sending to a serious referee so the recursion can be verified and the experiments can be stress-tested on more adversarial orderings.

Referee Report

2 major / 2 minor

Summary. The paper introduces Manifold k-NN, a generalization of dynamic programming-based nearest-neighbor search (DP-NNS) to arbitrary k-NN queries on point clouds sampled from 2-manifolds. It rests on a geometric observation that if p_i is the nearest neighbor of query q then the second nearest neighbor lies in the prefix P_{1:i-1} or in p_i's successor list; this observation is extended recursively to produce a candidate set from which the k nearest neighbors are extracted. The method is claimed to deliver 1-10x speedups versus kd-trees on volume-to-surface queries, to support zero-overhead dynamic prefix queries on any P_{1:m}, and to handle point deletions via local Delaunay updates, with supporting experiments on geometric datasets.

Significance. If the recursive candidate-set construction is provably complete and the reported speedups are reproducible, the work would provide a useful, manifold-aware primitive for k-NN in geometry processing and graphics pipelines, especially where dynamic updates or prefix queries are required. The open-source release further strengthens potential impact.

major comments (2)

[Abstract / §3] Abstract and §3 (geometric observation): the recursive extension of the stated property to arbitrary k does not obviously guarantee that every true k-th neighbor is included in the generated candidate pool. If the fixed ordering produced by incremental Voronoi refinement leaves some manifold directions outside the successor lists of earlier points, a later point p_j (j>i) that is the actual k-th neighbor can be omitted, producing an incorrect result rather than merely a slower one. A formal proof or exhaustive counter-example search on low-dimensional manifolds is needed to establish completeness.
[Experimental section] Experimental section (results tables and figures): the claimed 1-10x speedups are reported without baseline implementation details, variance across runs, or explicit description of how kd-tree and other comparators were configured (e.g., leaf size, distance metric). Without these, it is impossible to determine whether the gains are robust or sensitive to post-hoc tuning and dataset selection.

minor comments (2)

[§2] Notation: the distinction between the full point set P and the prefix P_{1:m} should be introduced with a single consistent symbol set in the first paragraph of the method section.
[Abstract] The abstract states that source code is available, but the manuscript does not indicate which version or commit was used for the reported timings; this should be added for reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments on our manuscript. We address each major comment below and describe the revisions we will make.

read point-by-point responses

Referee: [Abstract / §3] Abstract and §3 (geometric observation): the recursive extension of the stated property to arbitrary k does not obviously guarantee that every true k-th neighbor is included in the generated candidate pool. If the fixed ordering produced by incremental Voronoi refinement leaves some manifold directions outside the successor lists of earlier points, a later point p_j (j>i) that is the actual k-th neighbor can be omitted, producing an incorrect result rather than merely a slower one. A formal proof or exhaustive counter-example search on low-dimensional manifolds is needed to establish completeness.

Authors: We appreciate the referee's concern regarding the completeness of the recursive candidate-set construction. The manuscript extends the DP-NNS geometric observation recursively to arbitrary k, but we acknowledge that an explicit inductive argument is required to confirm that no true k-th neighbor is omitted. In the revised manuscript we will add a formal proof by induction in Section 3: the base case (k=1) follows from the original DP-NNS property; the inductive step shows that the k-th neighbor must reside either in the prefix up to the (k-1)-th neighbor or in one of the successor lists of those neighbors, because the incremental Voronoi ordering on the manifold ensures that all locally adjacent directions are represented in the successor structures. We will also include results from an exhaustive enumeration on low-dimensional manifolds (unit spheres and tori, 500–2000 points) demonstrating that the candidate pool always contains the true k nearest neighbors. These additions will be placed in the main text and an appendix. revision: yes
Referee: [Experimental section] Experimental section (results tables and figures): the claimed 1-10x speedups are reported without baseline implementation details, variance across runs, or explicit description of how kd-tree and other comparators were configured (e.g., leaf size, distance metric). Without these, it is impossible to determine whether the gains are robust or sensitive to post-hoc tuning and dataset selection.

Authors: We agree that the experimental section requires additional implementation and statistical details to support reproducibility and robustness claims. In the revised manuscript we will expand the experimental section to specify: kd-tree leaf size (set to 10), distance metric (Euclidean), and all other configuration parameters; standard deviation and min/max timings computed over 20 independent runs per dataset and query type; and the precise procedure used to generate and subsample the geometric datasets. We will also update the public GitHub repository with the exact scripts and configuration files that produced the reported figures and tables. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation rests on independent geometric observation

full rationale

The paper's central algorithmic scheme is founded on an explicitly stated geometric observation regarding nearest-neighbor locations relative to prefix sets and successor lists inherited from the DP-NNS framework. This observation is presented as a first-principles property of the point ordering and Voronoi refinement, not as a quantity fitted to data, defined in terms of the output k-NN result, or justified solely by self-citation. The recursive extension to arbitrary k is an algorithmic generalization rather than a reduction that equates the claimed result to its inputs by construction. No equations or steps in the abstract reduce the speedup claim or dynamic-query support to fitted constants or prior self-referential definitions. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method rests on one domain-specific geometric property and standard assumptions about manifold sampling; no free parameters or new invented entities are introduced.

axioms (1)

domain assumption If p_i is the nearest neighbor of q, then the second nearest neighbor lies in P_{1:i-1} or in p_i's successor list (and recursively for higher k).
This is the load-bearing geometric observation stated in the abstract that enables the recursive scheme.

pith-pipeline@v0.9.0 · 5652 in / 1212 out tokens · 45182 ms · 2026-05-08T01:50:46.146560+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 16 canonical work pages · 1 internal anchor

[1]

InProceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing(Aachen, Germany)(SGP ’03)

Approximating and intersecting surfaces from points. InProceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing(Aachen, Germany)(SGP ’03). Eurographics Association, Goslar, DEU, 230–239. M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and C.T. Silva

2003
[2]

doi:10.1109/TVCG.2003.1175093 Dominique Attali, Jean-Daniel Boissonnat, and André Lieutier

Computing and rendering point set surfaces.IEEE Transactions on Visualization and Computer Graphics9, 1 (2003), 3–15. doi:10.1109/TVCG.2003.1175093 Dominique Attali, Jean-Daniel Boissonnat, and André Lieutier

work page doi:10.1109/tvcg.2003.1175093 2003
[3]

InProceedings of the Nineteenth Annual Symposium on Computational Geometry(San Diego, California, USA)(SCG ’03)

Complexity of the delaunay triangulation of points on surfaces the smooth case. InProceedings of the Nineteenth Annual Symposium on Computational Geometry(San Diego, California, USA)(SCG ’03). Association for Computing Machinery, New York, NY, USA, 201–210. doi:10.1145/777792.777823 Ma Baorui, Han Zhizhong, Liu Yu-Shen, and Zwicker Matthias

work page doi:10.1145/777792.777823
[4]

doi:10.1145/93605.98741 Jon Louis Bentley

The R*-tree: an efficient and robust access method for points and rectangles.SIGMOD Rec.19, 2 (May 1990), 322–331. doi:10.1145/93605.98741 Jon Louis Bentley

work page doi:10.1145/93605.98741 1990
[5]

Multidimensional binary search trees used for associative searching

Multidimensional binary search trees used for associative searching.Commun. ACM18, 9 (sep 1975), 509–517. doi:10.1145/361002.361007 P.J. Besl and Neil D. McKay

work page doi:10.1145/361002.361007 1975
[6]

Besl and Neil D

A method for registration of 3-D shapes.IEEE Transactions on Pattern Analysis and Machine Intelligence14, 2 (1992), 239–256. doi:10.1109/34.121791 Jose Luis Blanco and Pranjal Kumar Rai

work page doi:10.1109/34.121791 1992
[7]

http://www.boost.org/

Boost C++ Libraries. http://www.boost.org/. Last accessed 2015-06-30. Alexandre Boulch and Renaud Marlet

2015
[8]

J.24, 2 (01 1981), 162–166

Computing Dirichlet tessellations*.Comput. J.24, 2 (01 1981), 162–166. Philipp Erler, Paul Guerrero, Stefan Ohrhallinger, Niloy J. Mitra, and Michael Wimmer

1981
[9]

37–55 (05 2021)

Points2Surf: Learning Implicit Surfaces from Point Clouds. InComputer Vision – ECCV 2020, Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (Eds.). Springer International Publishing, Cham, 108–124. doi:10.1007/978-3-030- 58558-7_7 Antonin Guttman

work page doi:10.1007/978-3-030- 2020
[10]

In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data(Boston, Massachusetts)(SIGMOD ’84)

R-trees: a dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data(Boston, Massachusetts)(SIGMOD ’84). Association for Computing Machinery, New York, NY, USA, 47–57. doi:10.1145/602259.602266 Susan Hert and Michael Seel

work page doi:10.1145/602259.602266 1984
[11]

InCGAL User and Reference Manual(5.6.1 ed.)

dD Convex Hulls and Delaunay Triangulations. InCGAL User and Reference Manual(5.6.1 ed.). CGAL Editorial Board. https: //doc.cgal.org/5.6.1/Manual/packages.html#PkgConvexHullD Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1992a. Surface reconstruction from unorganized points.SIGGRAPH Comput. Graph. 26, 2 (jul 1992), 71–78. do...

work page doi:10.1145/142920.134011 1992
[12]

OctoMap: an efficient probabilistic 3D mapping framework based on octrees

OctoMap: an efficient probabilistic 3D mapping framework based on octrees.Auton. Robots34, 3 (April 2013), 189–206. doi:10.1007/s10514-012-9321-0 Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Marc Alexa, Denis Zorin, and Daniele Panozzo

work page doi:10.1007/s10514-012-9321-0 2013
[13]

arXiv preprint arXiv:2308.16139(2023)

MedShapeNet–A Large-Scale Dataset of 3D Medical Shapes for Computer Vision. arXiv preprint arXiv:2308.16139(2023). Niloy J. Mitra and An Nguyen

work page arXiv 2023
[14]

InProceedings of the Nineteenth Annual Symposium on Computational Geometry (San Diego, California, USA)(SCG ’03)

Estimating surface normals in noisy point cloud data. InProceedings of the Nineteenth Annual Symposium on Computational Geometry (San Diego, California, USA)(SCG ’03). Association for Computing Machinery, New York, NY, USA, 322–328. doi:10.1145/777792.777840 Andrey Prokopenko, Daniel Arndt, Damien Lebrun-Grandié, and Bruno Turcksin

work page doi:10.1145/777792.777840
[15]

The ArborX Library: Version 2.0.ACM Trans. Math. Software51 (2025), 1 –

2025
[16]

Georges Voronoi

A comparative study of k-nearest neighbour techniques in crowd simulation.Computer Animation and Virtual Worlds28, 3-4 (2017), e1775. Georges Voronoi

2017
[17]

Premier mémoire

Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives parfaites.Journal für die reine und angewandte Mathematik (Crelles Journal)1908, 133 (1908), 97–102. doi:doi:10.1515/crll.1908.133.97 Pengfei Wang, Jiantao Song, Shiqing Xin, Shuangmin Chen, Changh...

work page doi:10.1515/crll.1908.133.97 1908
[18]

doi:10.1109/TPAMI.2025.3610211 Huibiao Wen, Guilong He, Rui Xu, Shuangmin Chen, Shiqing Xin, Zhenyu Shu, Taku Komura, Jieqing Feng, Wenping Wang, and Changhe Tu

Efficient Nearest Neighbor Search Using Dynamic Programming.IEEE Transactions on Pattern Analysis and Machine Intelligence(2025), 1–16. doi:10.1109/TPAMI.2025.3610211 Huibiao Wen, Guilong He, Rui Xu, Shuangmin Chen, Shiqing Xin, Zhenyu Shu, Taku Komura, Jieqing Feng, Wenping Wang, and Changhe Tu

work page doi:10.1109/tpami.2025.3610211 2025
[19]

InProceedings of the Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers (SIGGRAPH Conference Papers ’25)

Feature-Preserving Mesh Repair via Restricted Power Diagram. InProceedings of the Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers (SIGGRAPH Conference Papers ’25). Association for Computing Machinery, New York, NY, USA, Article 150, 11 pages. doi:10.1145/3721238.3730671 Qiangeng Xu, Zexiang Xu, Julien Ph...

work page doi:10.1145/3721238.3730671 2022
[20]

pseudo-genus

Thingi10K: A Dataset of 10,000 3D-Printing Models.arXiv preprint arXiv:1605.04797(2016). Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun

work page arXiv 2016
[21]

Open3D: A Modern Library for 3D Data Processing

Open3D: A Modern Library for 3D Data Processing.arXiv:1801.09847(2018). ACM Trans. Graph., Vol. 45, No. 4, Article

work page internal anchor Pith review arXiv 2018
[22]

Publication date: May 2026

2026