Near-Optimal Dynamic Data Structures for Maximum Depth and Klee’s Measure of Boxes

We start by recalling the main idea behind the 2D data structure of [30]. It partitions the plane into $r$ vertical strips so that each strip contains $O(n/r)$ rectangle corners, and maintains the maximum depth inside each strip separately. Although $\mathrm{\Omega }(n)$ rectangles may intersect a fixed strip, all but $O(n/r)$ of them have no corner in it; we call these rectangles good (for the strip), and the remaining $O(n/r)$ rectangles bad. Inside the strip, every good rectangle spans the strip in the $x$-direction and is therefore equivalent to an interval on the $y$-axis. This reduces the subproblem inside the strip to maintaining the maximum depth of a dynamic set of (weighted) intervals: updates caused by good rectangles take only $\tilde{O}(1)$ time, while updates caused by bad rectangles take $\tilde{O}(n/r)$ time, since there are only $O(n/r)$ bad rectangles whose contribution must be recomputed. Moreover, each rectangle is bad for only $O(1)$ strips (namely those containing its left or right vertical side), and is good for all other strips. Overall, the update time is $\tilde{O}(r+n/r)$, which becomes $\tilde{O}(\sqrt{n})$ by setting $r=\sqrt{n}$.

A natural goal in ${ℝ}^d$ is to replicate the same high-level principle: partition space so that most boxes behave “one-dimensionally” inside each region (and can be maintained cheaply), while only a small set of boxes interacts with the region boundaries. Two straightforward generalizations break down for essentially the same reason: the contribution of the boundary-interacting (“bad”) boxes can have prohibitively large combinatorial complexity. There are multiple natural generalizations of this approach to higher dimensions; however, none of them guarantees the desired bounds.

• $\mathrm{■}$

  Partition into $r$ slabs along one axis: Partition ${ℝ}^d$ into $r$ slab regions $S_1,\mathrm{\dots },S_r$ perpendicular to the $x_1$-axis, each containing $O(n/r)$ box corners. Inside a slab $S_i$, good boxes are those with no corner in $S_i$; they span the slab in the $x_1$-direction and thus reduce to $(d-1)$-dimensional boxes via projection. The difficulty is with the bad boxes: their contribution inside $S_i$ can be described by a piecewise-constant depth function over ${ℝ}^{d-1}$ whose rectilinear decomposition may require $\mathrm{\Omega }({(n/r)}^{d-1})$ regions in the worst case (because arrangements of $t$ boxes in ${ℝ}^{d-1}$ can have complexity $\mathrm{\Omega }(t^{d-1})$). Thus, even assuming optimal lower-dimensional dynamic structures, the induced subproblem sizes are too large to support the target update time.

• $\mathrm{■}$

  Partition into $r^{d\mathbf{-}\mathrm{𝟏}}$ cells in the first $d\mathbf{-}\mathrm{𝟏}$ dimensions: Choose $r-1$ hyperplanes perpendicular to each of the first $d-1$ coordinate axes, so that these hyperplanes form a grid partition of ${ℝ}^d$ into $r^{d-1}$ cells, each of the form $\mathrm{\square }\times ℝ$, where $\mathrm{\square }\subseteq {ℝ}^{d-1}$ is a $(d-1)$-dimensional axis-parallel box. Inside a fixed cell $\mathrm{\square }\times ℝ$, a box is good if it spans the cell in the first $d-1$ coordinates, i.e., it completely covers $\mathrm{\square }$. Restricted to the cell, such a box contributes exactly one interval on the last axis and can be maintained with a dynamic maximum-depth data structure for intervals. The bottleneck is the remaining bad boxes, namely those that intersect $\mathrm{\square }$ but do not cover it, so some side facet of the box crosses the base $\mathrm{\square }$. A direct adaptation would handle these bad boxes in each affected cell by sweeping along the last axis and repeatedly invoking a $(d-1)$-dimensional dynamic maximum-depth subroutine. Even assuming optimal lower-dimensional update bounds, this becomes too expensive once summed over the $\mathrm{\Theta }(r^{d-2})$ cells whose bases can be intersected by the boundary of a single updated box.

At a high-level, we also follow the grid partition into cells of the form $\mathrm{\square }\times ℝ$, and we retain the same “good boxes $\Rightarrow$ interval updates” principle. The key new ingredient is a structure-sensitive way to process the bad boxes within a fixed cell.

Fix a cell $\mathrm{\square }\subseteq {ℝ}^{d-1}$, and consider the set of bad boxes whose projections intersect $\mathrm{\square }$ but do not cover it. Our data structure represents their contribution to the depth inside $\mathrm{\square }\times ℝ$ by a piecewise-constant function on the last coordinate (equivalently, by a set of weighted (type-2) intervals, one per piece). Thus, for a cell $\mathrm{\square }\times ℝ$, the total depth reduces to the maximum depth of a set of weighted intervals on the last axis: type-1 intervals coming from good boxes (weight $1$) plus the type-2 intervals capturing the bad-box contribution.

The core task in an update is therefore the following: when the bad-box set for a cell changes, we must recompute the new inside-$\mathrm{\square }$ depth function (and hence the new set of type-2 intervals) efficiently. We accomplish this via an offline subroutine that further refines $\mathrm{\square }$ by inserting additional axis-parallel hyperplanes so that, inside every resulting subcell, each bad box becomes equivalent to a slab in ${ℝ}^{d-1}$ (i.e., it is bounded in exactly one of the first $d-1$ directions and is either fully present or fully absent in the other directions throughout the subcell). Once this holds, the contribution of the bad boxes inside each subcell reduces to a one-dimensional interval problem on the last axis.

The key idea to keep the refinement small is to avoid cutting at every bad-box endpoint in every partially overlapping direction. Instead, we choose an ordering (permutation) $\sigma$ of the first $d-1$ coordinate axes. For a given bad box, we treat the earliest axis (in $\sigma$-order) along which it only partially overlaps $\mathrm{\square }$ as its active direction (the slab direction), and we cut at the box endpoints only in the later partially overlapping directions. Equivalently, the box charges every partially overlapping direction except its first one under $\sigma$. In the formal development, this choice is captured by the indicators ${\varphi }_{\sigma ,\mathrm{\square }}(\cdot ,i)$ and the counts ${\mathrm{\Phi }}_{\sigma ,\mathrm{\square }}(\cdot ,i)=1+\sum {\varphi }_{\sigma ,\mathrm{\square }}(\cdot ,i)$. For a fixed $\sigma$, the number of inserted hyperplanes perpendicular to axis $i$ is proportional to ${\mathrm{\Phi }}_{\sigma ,\mathrm{\square }}(\cdot ,i)-1$, and the number of resulting subcells is bounded by $O({\prod }_i{\mathrm{\Phi }}_{\sigma ,\mathrm{\square }}(\cdot ,i))$, which also governs the running time of the offline subroutine.

In the dynamic data structure, we maintain the values ${\mathrm{\Phi }}_{\sigma ,\mathrm{\square }}(\cdot ,i)$ for every cell $\mathrm{\square }$, every axis $i\in [d-1]$, and every permutation $\sigma$. When an update changes the bad-box set in a cell, we pick the permutation $\sigma$ that minimizes the product bound ${\prod }_i{\mathrm{\Phi }}_{\sigma ,\mathrm{\square }}(\cdot ,i)$ and invoke the offline subroutine under this choice to compute the updated inside-$\mathrm{\square }$ depth function (and hence the new type-2 intervals) for that cell. Meanwhile, updates from good boxes remain fast interval insertions/deletions (type-1 updates).

The remaining challenge is to argue that the total cost of these offline computations over all cells affected by a single box update is bounded by $\tilde{O}(n^{(d-1)/2})$. This is where the main charging analysis enters. The affected cells lie on $O(d)$ “slices” of the grid determined by the facets of the projected box: fixing a coordinate $t\in [d-1]$ and a slab index $a\in [r]$ specifies a family of cells $V_t(a)$. A global charging argument relates each local quantity ${\mathrm{\Phi }}_{\sigma ,{\mathrm{\square }}_v}(\cdot ,i)$ to the distribution of box corners among these slices and shows that, for any slice $V_t(a)$, choosing an order $\sigma$ whose first element is $t$ yields a strong bound on ${\sum }_{\mathrm{\square }\in V_t(a)}{\prod }_i{\mathrm{\Phi }}_{\sigma ,\mathrm{\square }}(\cdot ,i)$ (Lemma 11). Combining this with the fact that each affected cell contains only $O(n/r)$ bad boxes yields the desired amortized update time after setting $r=\sqrt{n}$.

In designing our algorithm, we require an efficient dynamic maximum-depth data structure for slabs, i.e., boxes that are bounded in exactly one dimension. Formally, a slab $L$ in ${ℝ}^c$ is a box such that there exists exactly one index $i\in [c]$ satisfying ${\mathrm{𝐩𝐫𝐨𝐣}}_i(L)\ne (-\mathrm{\infty },\mathrm{\infty })$.

If we have a dynamic set $ℒ$ of slabs in ${ℝ}^c$ that are all bounded in the same dimension, then maintaining the maximum depth of $ℒ$ reduces to maintaining the maximum depth of a dynamic set of intervals and can be done with logarithmic update time. Moreover, the following observation implies that even if the slabs in $ℒ$ are bounded in different dimensions, we can still maintain the maximum depth of $ℒ$ with logarithmic update time by handling each dimension separately.

Let $\mathrm{\square }$ be a box in ${ℝ}^c$. We say a box $B$ in ${ℝ}^c$ is nontrivial in dimension $i\in [c]$ with respect to $\mathrm{\square }$ if ${\mathrm{𝐩𝐫𝐨𝐣}}_i(\mathrm{\square })\cap {\mathrm{𝐩𝐫𝐨𝐣}}_i(B)\ne \mathrm{\varnothing }$ and ${\mathrm{𝐩𝐫𝐨𝐣}}_i(\mathrm{\square })⊈{\mathrm{𝐩𝐫𝐨𝐣}}_i(B)$. For a permutation $\sigma$ of $[c]$, an index $i\in [c]$, and a box $B$ in ${ℝ}^c$, we define ${\varphi }_{\sigma ,\mathrm{\square }}(B,i)=1$ if both of the following conditions hold:

• $\mathrm{■}$

  $B$ is nontrivial in dimension $i$ with respect to $\mathrm{\square }$,

• $\mathrm{■}$

  there exists such that $B$ is nontrivial in dimension $j$ with respect to $\mathrm{\square }$.

Otherwise, ${\varphi }_{\sigma ,\mathrm{\square }}(B,i)=0$. For a set $ℬ$ of boxes in ${ℝ}^c$, define ${\mathrm{\Phi }}_{\sigma ,\mathrm{\square }}(ℬ,i)=1+{\sum }_{B\in ℬ}{\varphi }_{\sigma ,\mathrm{\square }}(B,i)$.

In the preprocessing, for each dimension $i\in [d-1]$, we construct a set ${\mathscr{H}}_i$ of $r-1$ hyperplanes in ${ℝ}^d$ perpendicular to the $x_i$-axis such that, after sorting the hyperplanes along the $x_i$-axis, the number of corners of boxes in $ℬ$ lying between any two consecutive hyperplanes is $O(n/r)$. Let $\mathscr{H}:={\bigcup }_{i=1}^{d-1}{\mathscr{H}}_i$. The hyperplanes in $\mathscr{H}$ partition ${ℝ}^d$ into $r^{d-1}$ regions, which we call cells. We index cells by vectors $\overrightarrow{v}=(a_1,\mathrm{\dots },a_{d-1})\in {[r]}^{d-1}$, where $a_i$ indicates the position of the cell along dimension $i$ (i.e., the cell lies between the $(a_i-1)$-st and $a_i$-th hyperplanes in ${\mathscr{H}}_i$, with the two outermost slabs treated as unbounded). Since we do not introduce hyperplanes perpendicular to the $x_d$-axis, each cell is of the form $\mathrm{\square }\times ℝ$ for a box $\mathrm{\square }\subseteq {ℝ}^{d-1}$. For each $\overrightarrow{v}\in {[r]}^{d-1}$, let ${\mathrm{\square }}_{\overrightarrow{v}}$ denote the unique box in ${ℝ}^{d-1}$ such that the corresponding cell is ${\mathrm{\square }}_{\overrightarrow{v}}\times ℝ$.

By the standard periodic reconstruction trick, we may assume that $|ℬ|=\mathrm{\Theta }(n)$ throughout the reconstruction period. For simplicity, we also assume that, throughout the period, for each $i\in [d-1]$, the number of corners of boxes in $ℬ$ between any two consecutive hyperplanes in ${\mathscr{H}}_i$ remains $O(n/r)$. This assumption can be removed by applying the same splitting procedure as in [30]; we defer these implementation details to Appendix A.

For each $\overrightarrow{v}\in {[r]}^{d-1}$, our data structure maintains the following information:

• $\mathrm{■}$

  ${\mathrm{\Phi }}_{\sigma ,{\mathrm{\square }}_{\overrightarrow{v}}}({\mathrm{𝐩𝐫𝐨𝐣}}_{[d-1]}(ℬ),i)$ for all permutations $\sigma$ of $[d-1]$ and all $i\in [d-1]$.

• $\mathrm{■}$

  The subset ${ℬ}_{\overrightarrow{v}}:=\{B\in ℬ:{\mathrm{\square }}_{\overrightarrow{v}}\cap {\mathrm{𝐩𝐫𝐨𝐣}}_{[d-1]}(B)\ne \mathrm{\varnothing }\text{ and }{\mathrm{\square }}_{\overrightarrow{v}}⊈{\mathrm{𝐩𝐫𝐨𝐣}}_{[d-1]}(B)\}\subseteq ℬ$.

• $\mathrm{■}$

  A dynamic maximum-depth data structure ${𝐃}_{\overrightarrow{v}}$ for weighted intervals, storing a multiset ${ℐ}_{\overrightarrow{v}}$ that consists of:

  • –

    the interval ${\mathrm{𝐩𝐫𝐨𝐣}}_d(B)$ with weight $1$, for every $B\in ℬ$ with ${\mathrm{\square }}_{\overrightarrow{v}}\subseteq {\mathrm{𝐩𝐫𝐨𝐣}}_{[d-1]}(B)$; these are called type-1 intervals,

  • –

    the interval $P$ with weight ${\delta }_{{\mathrm{\square }}_{\overrightarrow{v}}}^{{ℬ}_{\overrightarrow{v}}}(P)$, for every piece $P$ of the function ${\delta }_{{\mathrm{\square }}_{\overrightarrow{v}}}^{{ℬ}_{\overrightarrow{v}}}$; these are called type-2 intervals.

The basic correspondence between ${ℐ}_{\overrightarrow{v}}$ and the inside-${\mathrm{\square }}_{\overrightarrow{v}}$ depth function is easy to establish.

We show that each update of our data structure can be processed in $\tilde{O}({(n/r)}^{d-1}+r^{d-1})$ time. Setting $r=\sqrt{n}$ then yields the desired bound $\tilde{O}(n^{(d-1)/2})$.

Consider an update that inserts a new box $B^{\ast }$ or deletes an existing box $B^{\ast }$. First observe that, for every $\overrightarrow{v}\in {[r]}^{d-1}$ such that ${ℬ}_{\overrightarrow{v}}$ does not change, the corresponding local update costs only $\tilde{O}(1)$ time (it consists of maintaining counters and possibly inserting/deleting a single type-1 interval). In total, this contributes $\tilde{O}(r^{d-1})$ time. It therefore suffices to focus on those $\overrightarrow{v}\in {[r]}^{d-1}$ for which ${ℬ}_{\overrightarrow{v}}$ changes; let $V^{\ast }\subseteq {[r]}^{d-1}$ denote this set. Note that $V^{\ast }$ consists exactly of the vectors $\overrightarrow{v}$ for which ${\mathrm{\square }}_{\overrightarrow{v}}$ intersects the boundary of ${\mathrm{𝐩𝐫𝐨𝐣}}_{[d-1]}(B^{\ast })$. For $\overrightarrow{v}\in V^{\ast }$, all steps of the update can still be performed in $\tilde{O}(1)$ time except: (i) recomputing ${\delta }_{{\mathrm{\square }}_{\overrightarrow{v}}}^{{ℬ}_{\overrightarrow{v}}}$ via Corollary 6, and (ii) deleting the old type-2 intervals from ${𝐃}_{\overrightarrow{v}}$ and inserting the new ones. Since ${\delta }_{{\mathrm{\square }}_{\overrightarrow{v}}}^{{ℬ}_{\overrightarrow{v}}}$ has $O(|{ℬ}_{\overrightarrow{v}}|)$ pieces, step (ii) costs $\tilde{O}(|{ℬ}_{\overrightarrow{v}}|)$ time, which is dominated (up to logarithmic factors) by the cost of step (i). Thus, it suffices to bound the total cost of computing ${\delta }_{{\mathrm{\square }}_{\overrightarrow{v}}}^{{ℬ}_{\overrightarrow{v}}}$ for all $\overrightarrow{v}\in V^{\ast }$.

Let $ℬ$ denote the set of boxes after the insertion/deletion of $B^{\ast }$. For $i\in [d-1]$ and $a\in [r]$, define

Intuitively, the cells ${\mathrm{\square }}_{\overrightarrow{v}}\times ℝ$ with $\overrightarrow{v}\in V_i(a)$ are precisely those whose $i$-th coordinate is $a$. Define ${\gamma }_i(a):={\sum }_{\overrightarrow{v}\in V_i(a)}\left|\mathrm{𝖼𝗈𝗋}(ℬ)\cap ({\mathrm{\square }}_{\overrightarrow{v}}\times ℝ)\right|$, i.e., the number of corners of boxes in $ℬ$ lying in these cells. For $i,j\in [d-1]$ and $a,b\in [r]$, define $V_{i,j}(a,b)$ and ${\gamma }_{i,j}(a,b)$ similarly. The following basic properties are immediate from the construction.

Combining Item 1 and Item 3 yields $|{ℬ}_{\overrightarrow{v}}|=O(n/r)$ for all $\overrightarrow{v}\in {[r]}^{d-1}$, and in particular for all $\overrightarrow{v}\in V^{\ast }$. By Corollary 6, computing ${\delta }_{{\mathrm{\square }}_{\overrightarrow{v}}}^{{ℬ}_{\overrightarrow{v}}}$ takes time

where the minimum is over permutations $\sigma$ of $[d-1]$. Thus, the remaining difficulty is to bound the multiplicative factor ${\min }_{\sigma }{\prod }_{i=1}^{d-1}{\mathrm{\Phi }}_{\sigma ,{\mathrm{\square }}_{\overrightarrow{v}}}({\mathrm{𝐩𝐫𝐨𝐣}}_{[d-1]}({ℬ}_{\overrightarrow{v}}),i)$ in aggregate over $\overrightarrow{v}\in V^{\ast }$. A per-cell bound is too weak; instead we carry out a global analysis. The key is Lemma 11, which is based on the following relation between the $\mathrm{\Phi }$-values and the $\gamma$-values.