2026-07-23T21:03:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22901 2025-10-02T13:36:56Z ddc:004 open_access

Dynamic Unit-Disk Range Reporting Wang, Haitao Zhao, Yiming Unit disks range reporting range emptiness alpha-hulls dynamic data structures shallow cuttings 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+ε} n) amortized insertion time, O(log^{5+ε} n) amortized deletion time, and O(log² n/log log n+k) query time, where ε 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² n) amortized insertion time, O(log⁴n) amortized deletion time, and O(log² n) query time. Our new data structure also uses O(n) space but can support each update in O(log^{1+ε} n) amortized time and support each query in O(log n) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang and Yiming Zhao 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.76 urn:nbn:de:0030-drops-229019 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.76 eng https://creativecommons.org/licenses/by/4.0/legalcode