New paper speeds up Delaunay-based nearest neighbor search with grid queries and parallel construction
ssh4net · x · 2026-11-14
Pengfei Wang, Shiqing Xin and Changhe Tu publish 'Delaunay-Based Nearest Neighbor Search with Grid-Accelerated Queries and Parallel Construction', targeting the common graphics setting where points lie on a surface manifold embedded in 3D space while queries fill the surrounding volume — a case where k-d trees and grids underperform. Building on DP-NNS, which traverses a successor DAG from incremental Delaunay construction, the paper adds grid-accelerated queries and parallel construction to fix DP-NNS's slow sequential build. Benchmarks (Bunny, Dragon, Lucy, etc.) show significantly lower preprocessing and 1-NN query times than the original DP-NNS, with applications in distance field computation, surface reconstruction and point cloud registration.
More from Research
- Open-source AV project plans interactive web book for learning navigation algorithms — 4310sy · 2026-11-14
- UC Davis Neuroprosthetics Lab Brings 8 Posters on Speech BCIs to SfN 2026 — neuro_engineer · 2026-11-14
- Independent scan: 185 of 265 open LLMs can infer their training GPU family — willdepue · 2026-11-14
- Latent Lookahead: training models to plan several steps ahead in hidden space — burkov · 2026-11-14
- Weekly paper pick: latent reasoning scales test-time compute via recurrent depth, not more tokens — LChoshen · 2026-11-14
- Yamanaka lab preprint: partial reprogramming outcomes diverge sharply by cell lineage — MaxUnfried · 2026-11-14