Abstract

In the nearest neighbor problem, we are given a set \(S\) of point sites that we want to store such that we can find the nearest neighbor of a (new) query point efficiently. In the dynamic version of the problem, the goal is to design a data structure that supports both efficient queries and updates, i.e. insertions and deletions in \(S\). This problem has been widely studied in various settings, ranging from points in the plane to more general distance measures and even points within simple polygons. When the sites do not live in the plane but in some domain, another dynamic problem arises: what happens if not the sites, but the domain itself is subject to updates?

Updating sites often results in local changes to the solution or data structure, while updating the domain may incur many global changes. For example, in the closest pair problem, inserting a point only requires us to check if this point is in the new closest pair, while updating the domain might change the distances between most pairs of points in our set. Presumably, this is the reason that this form of dynamization has received much less attention. Only some basic problems, such as shortest paths and ray shooting, have been studied in this setting.

Here, we tackle the nearest neighbor problem in a dynamic simple polygon. We allow insertions into both the set of sites and the polygon. An insertion in the polygon is the addition of a line segment starting at the boundary of the polygon. We present a near-linear size –in both the number of sites and the complexity of the polygon– data structure with sublinear update and query time. This is the first nearest neighbor data structure that allows for updates to the domain.

Corresponding Publications

Nearest Neighbor Searching in a Dynamic Simple Polygon

Sarita de Berg, Frank Staals

Proc. 41th Annual Symposium on Computational Geometry, 2025

Download Local Copy View Slides Export Citation

@inproceedings{nnDynamicPoly2025,
  author = {de Berg, Sarita and Staals, Frank},
  title = {Nearest Neighbor Searching in a Dynamic Simple Polygon},
  booktitle = {Proc. 41th Annual Symposium on Computational Geometry},
  year = {2025},
  location = {Kanazawa Japan},
  keywords = {data structure, polygonal domain, geodesic distance, shortest path},
  category = {geodesic},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.SoCG.2025.37},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2025.37},
}