Dynamic unit-disk range reporting

For a set $P$ of $n$ points in the plane and a value $r > 0$, the unit-disk range reporting problem is to construct a data structure so that given any query disk of radius $r$, all points of $P$ in the disk can be reported efficiently. We consider the dynamic version of the problem where point insertions and deletions of $P$ are allowed. The previous best method provides a data structure of $O(n \log n)$ space that supports $O(\log^{3 + \epsilon} n)$ amortized insertion time, $O(\log^{5 + \epsilon} n)$ amortized deletion time, and $O(\log^2 n / \log\log n + k)$ query time, where $\epsilon$ is an arbitrarily small positive constant and $k$ is the output size. In this paper, we improve the query time to $O(\log n + k)$ while keeping other complexities the same as before. A key ingredient of our approach is a shallow cutting algorithm for circular arcs, which may be interesting in its own right. A related problem that can also be solved by our techniques is the dynamic unit-disk range emptiness queries: Given a query unit disk, we wish to determine whether the disk contains a point of $P$. The best previous work can maintain $P$ in a data structure of $O(n)$ space that supports $O(\log^2 n)$ amortized insertion time, $O(\log^4 n)$ amortized deletion time, and $O(\log^2 n)$ query time. Our new data structure also uses $O(n)$ space but can support each update in $O(\log^{1 + \epsilon} n)$ amortized time and support each query in $O(\log n)$ time.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.