2026-09-08T02:21:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26423 2026-09-05T19:42:58Z ddc:004 open_access

Near-Optimal Dynamic Data Structures for Maximum Depth and Klee’s Measure of Boxes Bhore, Sujoy Suri, Subhash Xue, Jie Yang, Xiongxin Zhu, Jiumu dynamic algorithms maximum depth We study two fundamental geometric problems on a dynamic set of n axis-parallel boxes in d-dimensional space. The maximum depth problem asks for the largest number of boxes that contain a common point, whereas Klee’s measure problem asks for the volume of the union of the boxes. We present fully dynamic exact data structures for both problems achieving Õ(n^{(d-1)/2}) amortized update time. This update time is optimal for an exact dynamic algorithm, up to logarithmic factors, assuming the Combinatorial k-Clique Hypothesis. Previously, matching bounds were established only for d = 1 [Imai and Asano, J. Algo.'83], and for d = 2 [Suri, Xue, Yang, and Zhu, SoCG'25]. Our approach integrates a classic grid-based partition framework with a novel charging analysis that controls the cost of structure-sensitive offline routines within each cell. This argument allows us to perform a global aggregation of the update time, by circumventing the worst-case costs associated with individual cell updates. We believe this technique may be of independent interest for other dynamic geometric problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Subhash Suri and Jie Xue and Xiongxin Yang and Jiumu Zhu 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.34 urn:nbn:de:0030-drops-264230 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.34 eng https://creativecommons.org/licenses/by/4.0/legalcode