Incremental Planar Nearest Neighbor Queries with Optimal Query Time
John Iacono, Yakov Nekrich · 2025
Read Incremental Planar Nearest Neighbor Queries with Optimal Query Time by John Iacono, Yakov Nekrich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-07366.txt.
Description
John Iacono and Yakov Nekrich give a data structure for nearest neighbor search on a growing map, in this 2025 paper. The task is to find the closest stored point to any query point in the plane. Points can be added over time, but never removed in their setup.
No earlier structure paired fastest-possible queries with fast insertions. Their design answers queries in logarithmic time, the best that can be done. Insertions cost only slightly more than that. A new twist on fractional cascading, tuned to the geometry, makes it work. The method also fits other partly dynamic problems. Map and robotics systems that grow their data over time could use it.
Catalog record
| CREATOR | John Iacono, Yakov Nekrich |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-07366