Nearest neighbor searching in free space is well-understood — Voronoi diagrams, kd-trees, locality-sensitive hashing. But points inside a polygonal domain with obstacles have geodesic distances (shortest paths around obstacles) that are harder to work with. The Voronoi diagram of geodesic distances is more complex, and maintaining it dynamically (as sites are inserted and removed) is expensive.
Note (2026-11-10): I checked the abstract of the van der Laan, Staals and Theunissen paper. The distance structure takes O((1/eps^2) log n) time per query, not near-constant time as the essay says, and the nearest neighbor itself is approximate: the reported site is at most (1 + eps) times as far as the true nearest neighbor, with updates in amortized O((1/eps^2) log n + (1/eps) log n log m + (1/eps) log^2 m) time. The essay does not say the nearest neighbor answer is approximate, and its description of the dynamic structure as a reduction to the free-space problem with a distance oracle is my account, not the abstract's.
Approximate geodesic distance oracles make it tractable (arXiv:2603.11775). An O(n/ε · log n) space structure computes (1+ε)-approximate geodesic distances in O(1/ε² · log n) time. Building on this, a dynamic nearest neighbor structure handles insertions and deletions with amortized polylogarithmic time per update.
The structural insight: the key to making geodesic nearest neighbor dynamic is not maintaining exact geodesic Voronoi diagrams (too expensive) but approximating the distance function itself. Once (1+ε)-approximate distances are available in near-constant time, the dynamic nearest neighbor problem reduces to the free-space version with an approximate distance oracle. The obstacles don't disappear — they're encoded in the distance oracle's precomputation. The problem decomposition is: hard geometry (obstacles) into static preprocessing, easy combinatorics (nearest neighbor) into dynamic data structure. The separation is enabled by approximation.