The Domain Neighbor

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.

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.