Dynamic Maximum Depth of Geometric Objects

Given a set $𝒪$ of geometric shapes in ${ℝ}^d$, the depth of a point $p$ with respect to $𝒪$ is the number of objects in $𝒪$ that contain $p$. Formally, $\mathrm{𝖽𝖾𝗉}(p,𝒪)=|\{O\in 𝒪:p\in O\}|$. The maximum depth of the set $𝒪$ is denoted by $\mathrm{𝖽𝖾𝗉}(𝒪)={\max }_{p\in {ℝ}^d}\mathrm{𝖽𝖾𝗉}(p,𝒪)$. We often use $p^{\ast }$ to denote a point that maximizes the depth with respect to the set $𝒪$, i.e., $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒪)=\mathrm{𝖽𝖾𝗉}(𝒪)$, and ${𝒪}^{\ast }$ to denote a maximum geometric clique for $𝒪$, i.e., ${𝒪}^{\ast }=\{O\in 𝒪:p^{\ast }\in O\}$.

For a disk $D$, $\mathrm{𝖼𝗍𝗋}(D)$ and $\mathrm{𝗋𝖺𝖽}(D)$ denote its center and radius, respectively. This notation also holds for balls. In this paper, the fat object, which generalizes both rectangle and disk, is defined as follows: Let $O$ be a convex object in ${ℝ}^d$. Let $O_{\mathrm{in}}$ be the largest ball that is contained in $O$. We say $O$ is $\alpha$-fat, for some parameter $\alpha \ge 1$, if $O_{\mathrm{out}}$, the ball that is concentric with $O_{\mathrm{in}}$ and has radius $\mathrm{𝗋𝖺𝖽}(O_{\mathrm{out}})=\alpha \cdot \mathrm{𝗋𝖺𝖽}(O_{\mathrm{in}})$, contains $O$. We call the center of $O_{\mathrm{in}}$ the center of $O$ and $\mathrm{𝗋𝖺𝖽}(O_{\mathrm{in}})$ the in-radius of $O$.¹¹1There are different definitions of fat objects in different papers. One can easily show that our definition is equivalent to the others.

Let $ℒ$ be the set of all slabs occurred when processing the first $t$ operations. Consider the insertions in the $t$ operations. For each inserted rectangle $Q$, we charge it to the (at most) two slabs containing the corners of $R$ when $Q$ is inserted. Observe that a slab $L\in ℒ$ eventually splits only if it gets charged at least $n/r$ times. Indeed, $L$ contains $4n/r$ rectangle corners when it is created and contains $8n/r$ rectangle corners when it splits. Thus, from the time point that $L$ is created to the time point that $L$ splits, there are at least $n/r$ inserted rectangles which have corners in $L$, which implies that $L$ gets charged at least $n/r$ times. Since there can be at most $t$ inserted rectangles, the total number of charges is bounded by $2t$, which implies that the number of slab splitting is bounded by $2tr/n$. $◀$

Clearly, using the information stored in the slab data structures, we can compute in $O(r)$ time a point $p^{\ast }$ satisfying $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)=\mathrm{𝖽𝖾𝗉}(𝒬)$, as well as the value of $\mathrm{𝖽𝖾𝗉}(𝒬)$. More precisely, we just consider the points $p_1,\mathrm{\dots },p_r$ stored in the slab data structures (and their depths with respect to $𝒬$) and define $p^{\ast }$ as the one that maximizes its depth with respect to $𝒬$. Therefore, the remaining task now is to design efficient slab data structures.

Consider a slab $L$. We want to maintain a point $p\in L$ that maximizes $\mathrm{𝖽𝖾𝗉}(p,𝒬)$, as well as the value of $\mathrm{𝖽𝖾𝗉}(p,𝒬)$. Clearly, we can ignore the rectangles in $𝒬$ that are disjoint from $L$. Thus, in the following we assume that every rectangle in $𝒬$ intersects $L$. We classify the rectangles in $𝒬$ into two types: long rectangles and short rectangles. A rectangle is long if its four corners are all outside $L$ and is short if at least one corner is inside (the interior of) $L$. Let ${𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}\subseteq 𝒬$ and ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}\subseteq 𝒬$ be the sets of long and short rectangles in $𝒬$, respectively.

To maintain the maximum depth of $𝒬$ inside $L$, our main idea is to reduce the problem to maintaining the maximum depth of weighted intervals. Specifically, we shall construct a set $ℐ$ of weighted intervals from $𝒬$ such that the maximum depth of $𝒬$ inside $L$ is equal to the maximum (weighted) depth of $ℐ$. The construction is done as follows. For each long rectangle $Q=[x^{-},x^{+}]\times [y^{-},y^{+}]\in {𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}$, we include in $ℐ$ the interval $[x^{-},x^{+}]$ with weight $1$. For the set ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$ of short rectangles, we first define a depth function $f:ℝ\to \mathbb{N}$ as $f(r)={\max }_{p\in {\mathrm{\ell }}_r\cap L}\mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})$ where ${\mathrm{\ell }}_r$ is the vertical line with equation $x=r$. One can easily observe that $f$ is a piecewise-constant function with $O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ pieces, since the value of $f$ only changes at the $x$-coordinates of the corners of the short rectangles. Therefore, we can partition the real line $ℝ$ into $s=O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ intervals $I_1,\mathrm{\dots },I_s$ such that $f$ is a constant function when restricted to each $I_i$. Also, for each $I_i$, there is a $y$-coordinate $y_i\in ℝ$ such that $I_i\times \{y_i\}\subseteq L$ and $f(x)=\mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})$ for any $x\in I_i$ and $p\in I_i\times \{y_i\}$. Define a function $g:ℝ\to ℝ$ as $g(x)=y_i$ if $x\in I_i$. We include $I_1,\mathrm{\dots },I_s$ in $ℐ$ and set the weight of each $I_i$ to be $f(x)$ for an arbitrary $x\in I_i$. (See Figure 1 for an illustration.)

We observe the following simple fact.

We first prove that $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)=\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)$. By definition, $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)=\mathrm{𝖽𝖾𝗉}(p^{\ast },{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})+\mathrm{𝖽𝖾𝗉}(p^{\ast },{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})$. Note that a rectangle in ${𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}$ contains $p^{\ast }$ iff its corresponding weight-$1$ interval in $ℐ$ contains $x^{\ast }$. So $x^{\ast }$ is contained in exactly $\mathrm{𝖽𝖾𝗉}(p^{\ast },{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})$ weight-$1$ intervals corresponding to the rectangles in ${𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}$. Meanwhile, the total weight of the intervals containing $x^{\ast }$ which correspond to the rectangles in ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$ is equal to $f(x^{\ast })$. It follows that $\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)=\mathrm{𝖽𝖾𝗉}(p^{\ast },{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})+f(x^{\ast })$. As $p^{\ast }=(x^{\ast },g(x^{\ast }))$, we have $\mathrm{𝖽𝖾𝗉}(p^{\ast },{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})=f(x^{\ast })$ by the definition of $g$. Thus, $\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)=\mathrm{𝖽𝖾𝗉}(p^{\ast },{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})+\mathrm{𝖽𝖾𝗉}(p^{\ast },{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})=\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)$.

Since $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)\le {\max }_{p\in L}\mathrm{𝖽𝖾𝗉}(p,𝒬)$, it suffices to show that $\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)\ge {\max }_{p\in L}\mathrm{𝖽𝖾𝗉}(p,𝒬)$. Consider a point $p\in L$. Again, a rectangle in ${𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}$ contains $p$ iff its corresponding weight-$1$ interval in $ℐ$ contains $x(p)$. Also, $f(x(p))\ge \mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})$ by the definition of $f$. Therefore,

Since $\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)=\mathrm{𝖽𝖾𝗉}(ℐ)$, we have $\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)\ge \mathrm{𝖽𝖾𝗉}(x(p),ℐ)\ge \mathrm{𝖽𝖾𝗉}(p,𝒬)$. $◀$

For our slab data structure $𝒟(L)$, we can simply use the following result of Imai and Asano [14], which is a byproduct of their (static) algorithm for the maximum-depth problem for weighted rectangles.

Given $𝒬$, we first compute the set $ℐ$ as stated above (as well as the functions $f$ and $g$), and then build $𝒜(ℐ)$, i.e., the interval data structure of the above lemma on $ℐ$). $𝒜(ℐ)$ maintains $x^{\ast }\in ℝ$ satisfying $\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)=\mathrm{𝖽𝖾𝗉}(ℐ)$, as well as the value of $\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)$. The point we maintain is $p^{\ast }=(x^{\ast },g(x^{\ast }))$, which satisfies $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)={\max }_{p\in L}\mathrm{𝖽𝖾𝗉}(p,𝒬)$ by Fact 5. Also, the value of $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)$ is equal to $\mathrm{𝖽𝖾𝗉}(x^{\ast },ℐ)$ by Fact 5, and we can maintain the latter from $𝒜(ℐ)$.

Consider an insertion/deletion on $𝒬$, and let $Q$ be the inserted/deleted rectangle. If $Q$ is a long rectangle, we just need to insert/delete its corresponding weight-$1$ interval on $ℐ$ and update $𝒜(ℐ)$. If $Q$ is a short rectangle, the situation is more complicated and what we do is the following. First, we delete from $ℐ$ all intervals corresponding to the rectangles in the old ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$. Then we construct the intervals corresponding to the rectangles in the new ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$ (we shall show how to do this efficiently) and insert them to $ℐ$. Also, we re-compute the functions $f$ and $g$ corresponding to the new ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$. For both deletions and insertions on $ℐ$, we need to update $𝒜(ℐ)$ accordingly.

Next, we analyze the preprocessing time and update time for our slab data structure. To this end, we first show that one can compute the weighted intervals in $ℐ$ corresponding to the short rectangles, as well as the functions $f$ and $g$, in $O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|\log |{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ time. Indeed, we can directly apply the classical (static) rectangle maximum-depth algorithm [14] on ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$. The algorithm sweeps a vertical line $\mathrm{\ell }$ from left to right, and maintains the maximum depth of ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$ on $\mathrm{\ell }$. Therefore, it exactly computes the function $f$ and $g$, together with their piece intervals $I_1,\mathrm{\dots },I_s$. The running time of the algorithm is $O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|\log |{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$. The intervals in $ℐ$ corresponding to the long rectangles can be constructed directly. Overall, the time for constructing $ℐ$ is $O(|𝒬|\log |𝒬|)$, i.e., $O(n\log n)$. By Lemma 6, $𝒜(ℐ)$ can also be built in $O(n\log n)$ time as $|ℐ|=O(|𝒬|)$. So the preprocessing time of our slab data structure is $O(n\log n)$. For the update time, we need to distinguish long rectangles and short rectangles. Inserting/deleting a long rectangle corresponds to an insertion/deletion on $𝒜(ℐ)$ and thus can be done in $O(\log n)$ time. For the insertion/deletion of a short rectangle, we need to delete $O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ intervals from $ℐ$, re-compute the intervals corresponding to ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$ and the functions $f$ and $g$, and insert $O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ intervals to $ℐ$. The $O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ insertions/deletions on $𝒜(ℐ)$ can be done in $O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|\log n)$ time by Lemma 6, and the re-computation can be done in $O(|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|\log |{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ time as discussed above. As the number of rectangle corners in a slab is always $O(n/r)$, we have $|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|=O(n/r)$. Thus, the update time for a short rectangle is $O((n/r)\log n)$.

Using Lemma 7, we can now analyze the overall preprocessing time and update time of our data structure. Partitioning the plane into slabs can be done in $O(n\log n)$ time by sorting the corners of the rectangles in $𝒬$. Since there are $r$ slabs and each slab data structure can be constructed in $O(n\log n)$ time, the preprocessing time is $O(rn\log n)$. To analyze the update time, let $Q$ be the inserted/deleted rectangle. Note that there are at most two slabs in which $Q$ is a short rectangle. So among the updates of the slab data structures, there can be at most two updates for short rectangles and $O(r)$ updates for long rectangles. By Lemma 7, these updates take $O((n/r)\log n+r\log n)$ time. Also, rectangle insertions might cause slab splittings and for each slab splitting we need $O(n\log n)$ time to build the new slab data structures. By Fact 4, the time cost for slab splitting during the first $t$ operations is $O(tr\log n)$, and the amortized time cost is then $O(r\log n)$. Therefore, the overall (amortized) update time of our data structure is $O((n/r)\log n+r\log n)$. To balance the two terms, we set $r=\sqrt{n}$, yielding $O(\sqrt{n}\log n)$ update time. The preprocessing time is then $O(n^{1.5}\log n)$. Based on the above discussion, we have the following conclusion, which is the base case $k=1$ of Theorem 1.

Now we are able to prove Theorem 1 for a general $k\in \mathbb{N}$. As aforementioned, we apply induction on $k$. Lemma 8 gives us the base case $k=1$. Suppose there exists a $\frac{1}{k}$-approximate dynamic maximum-depth data structure for rectangles with $O(n^{1/(k+1)}\log n)$ (amortized) update time and $O(n^{1+1/(k+1)}\log n)$ preprocessing time. We want to show the existence of a $\frac{1}{k+1}$-approximate data structure with $O(n^{1/(k+2)}\log n)$ update time and $O(n^{1+1/(k+2)}\log n)$ preprocessing time.

As before, our data structure partitions the plane into $r$ slabs. The only difference occurs in the design of the slab data structures. Consider a slab $L$. We want our slab data structure for $L$ to maintain a point $p^{\ast }\in L$ satisfying that $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)\ge \frac{1}{k+1}\cdot {\max }_{p\in L}\mathrm{𝖽𝖾𝗉}(p,𝒬)$; this guarantees that our overall data structure achieves the approximation ratio $\frac{1}{k+1}$. Again, let ${𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}$ and ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$ denote the set of long and short rectangles in $𝒬$ with respect to $L$, respectively. Unlike in our exact data structure, we now handle ${𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}$ and ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$ separately. For long rectangles, we maintain a point $p_1^{\ast }\in L$ that maximizes $\mathrm{𝖽𝖾𝗉}(p_1^{\ast },{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})$. This can be done using exactly the same idea as before: map each long rectangle $Q=[x^{-},x^{+}]\times [y^{-},y^{+}]\in {𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}$ to the interval $[x^{-},x^{+}]$, and build $𝒜$ on these intervals. For short rectangles, we maintain a point $p_2^{\ast }\in L$ satisfying the condition that $\mathrm{𝖽𝖾𝗉}(p_2^{\ast },{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})\ge \frac{1}{k}\cdot {\max }_{p\in L}\mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})$. To this end, we build a $\frac{1}{k}$-approximate dynamic maximum-depth data structure on ${𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}$, which can give us the desired point $p_2^{\ast }$. By our induction hypothesis, there exists such a data structure with $O(n^{1/(k+1)}\log n)$ update time and $O(n^{1+1/(k+1)}\log n)$ preprocessing time. Define $p^{\ast }=p_1^{\ast }$ if $\mathrm{𝖽𝖾𝗉}(p_1^{\ast },{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})\ge \mathrm{𝖽𝖾𝗉}(p_2^{\ast },{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})$ and $p^{\ast }=p_2^{\ast }$ if . We observe the following.

Let $p\in L$ be a point that maximizes $\mathrm{𝖽𝖾𝗉}(p,𝒬)$. By definition, we have $\mathrm{𝖽𝖾𝗉}(p,𝒬)=\mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})+\mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})$. We consider two cases: $\mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})\ge \frac{1}{k+1}\mathrm{𝖽𝖾𝗉}(p,𝒬)$ and . If $\mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}})\ge \frac{1}{k+1}\mathrm{𝖽𝖾𝗉}(p,𝒬)$, we have

On the other hand, if , we must have $\mathrm{𝖽𝖾𝗉}(p,{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}})>\frac{k}{k+1}\mathrm{𝖽𝖾𝗉}(p,𝒬)$. In this case, we have

Therefore, we always have $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒬)\ge \frac{1}{k+1}\cdot \mathrm{𝖽𝖾𝗉}(p,𝒬)$. $◀$

The data structure for maintaining $p_1^{\ast }$ can be constructed in $O(|{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}|\log |{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}|)$ time and updated in $O(\log |{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}|)$ time, by Lemma 6. Furthermore, the data structure for maintaining $p_2^{\ast }$ can be constructed in $O({|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|}^{1+1/(k+1)}\log |{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ time and updated in $O({|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|}^{1/(k+1)}\log |{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|)$ time. Since $|{𝒬}_{\mathrm{𝗅𝗈𝗇𝗀}}|=O(n)$ and $|{𝒬}_{\mathrm{𝗌𝗁𝗈𝗋𝗍}}|=O(n/r)$, for each slab data structure, the preprocessing time is $O(n\log n+{(n/r)}^{1+1/(k+1)}\log (n/r))$ and the update time is $O(\log n)$ for long rectangles and $O({(n/r)}^{1/(k+1)}\log (n/r))$ for short rectangles. This implies that our overall data structure has preprocessing time $O(rn\log n+r{(n/r)}^{1+1/(k+1)}\log (n/r))$ and update time $O(r\log n+{(n/r)}^{1/(k+1)}\log (n/r))$. By setting $r=n^{1/(k+2)}$, we have the desired $\frac{1}{k+1}$-approximation data structure with $O(n^{1/(k+2)}\log n)$ amortized update time and $O(n^{1+1/(k+2)}\log n)$ preprocessing time.

See 1

Suppose we randomly sample a circular sector $X$ of $D$ with angle $(1-2\epsilon )\pi$, from the uniform distribution over the space of all such sectors. The probability that a specific point $p\in S$ is contained in $X$ is $1$ if $p$ is the center of $D$ and is $\frac{1}{2}-\epsilon$ otherwise. Therefore, $𝔼[|S\cap X|]\ge (\frac{1}{2}-\epsilon )\cdot |S|$, which in turn implies that there exists a sector $X$ of $D$ with angle $(1-2\epsilon )\pi$ for which $|S\cap X|\ge (\frac{1}{2}-\epsilon )\cdot |S|$. $◀$

Without loss of generality, we assume that the disks in $𝒟$ are unit disks. Let $p^{\ast }\in {\bigcap }_{D\in 𝒟}D$ and $P^{\ast }$ be the unit disk centered at $p^{\ast }$. Define $\mathrm{𝖼𝗍𝗋}(𝒟)$ as the set of the centers of the disks in $𝒟$. Since $p^{\ast }\in {\bigcap }_{D\in 𝒟}D$, we have $\mathrm{𝖼𝗍𝗋}(𝒟)\subseteq P^{\ast }$. By Fact 10, there is a circular sector $X$ of $P^{\ast }$ with angle $(1-2\epsilon )\pi$ such that $|\mathrm{𝖼𝗍𝗋}(𝒟)\cap X|\ge (\frac{1}{2}-\epsilon )\cdot |\mathrm{𝖼𝗍𝗋}(𝒟)|=(\frac{1}{2}-\epsilon )\cdot |𝒟|$. Suppose $u$ and $v$ are the two vertices of $X$ on the boundary of $P^{\ast }$. Define $o$ as the middle point of the segment connecting $u$ and $v$, and $D_o$ as the disk centered at $o$ with radius $1-\cos \epsilon \pi$. We claim that $\mathrm{𝖽𝖾𝗉}(p,𝒟)\ge \left(\frac{1}{2}-\epsilon \right)\cdot |𝒟|$ for any point $p\in D_o$. Consider an arbitrary point $p\in D_o$. Since the angle of $X$ is $(1-2\epsilon )\pi$, the distance between $o$ and $p^{\ast }$ is $\sin \epsilon \pi$. Also, the distance between $o$ and $u$ (resp., $v$) is $\cos \epsilon \pi$. Recall that by our assumption, which implies that . Therefore, the distance between $p$ and $p^{\ast }$ is at most , and the distance between $p$ and $u$ (resp., $v$) is at most $\cos \epsilon \pi +(1-\cos \epsilon \pi )=1$. Therefore, the unit disk centered at $p$ contains points $p^{\ast },u,v$, which further implies that it contains $X$. Consequently, the unit disks in $𝒟$ whose centers lie in $X$ contains $p$. We have $|\mathrm{𝖼𝗍𝗋}(𝒟)\cap X|\ge (\frac{1}{2}-\epsilon )\cdot |𝒟|$, which then implies that $\mathrm{𝖽𝖾𝗉}(p,𝒟)\ge \left(\frac{1}{2}-\epsilon \right)\cdot |𝒟|$. See Figure 2 for an illustration.

Now it suffices to show ${\mathrm{\Gamma }}_{\delta }(D)\cap D_o\ne \mathrm{\varnothing }$ for every $D\in 𝒟$. Note that the distance between $o$ and the center of $D$ is at most $2$, since $p^{\ast }\in D$ and $o\in P^{\ast }$. Furthermore, $D_o$ contains an axis-parallel square centered at $o$ with side-length $1-\cos \epsilon \pi$, as its radius is $1-\cos \epsilon \pi$. Since $1-\cos \epsilon \pi \ge \frac{1}{\delta }$, this square then contains a point in ${\mathrm{\Gamma }}_{\delta }(D)$, by our construction of ${\mathrm{\Gamma }}_{\delta }(D)$. Therefore, ${\mathrm{\Gamma }}_{\delta }(D)\cap D_o\ne \mathrm{\varnothing }$. $◀$

Let $p^{\ast }\in {ℝ}^2$ such that $\mathrm{𝖽𝖾𝗉}(p^{\ast },𝒟)=\mathrm{𝖽𝖾𝗉}(𝒟)$, and ${𝒟}^{\ast }=\{D\in 𝒟:p^{\ast }\in D\}$. Suppose $D_0\in {𝒟}^{\ast }$ is the smallest disk in ${𝒟}^{\ast }$. For each disk $D\in {𝒟}^{\ast }$, we can find a smaller disk $D^{\prime }\subseteq D$ with the same radius as $D_0$ such that $p^{\ast }\in D^{\prime }$. Let ${𝒟}^{\prime }$ be the set of all these disks. Then ${𝒟}^{\prime }$ is a set of congruent disks containing $p^{\ast }$, and $\mathrm{𝖽𝖾𝗉}(p,{𝒟}^{\prime })\le \mathrm{𝖽𝖾𝗉}(p,{𝒟}^{\ast })$ for any $p\in {ℝ}^2$. The former implies that ${\bigcap }_{D\in {𝒟}^{\prime }}D\ne \mathrm{\varnothing }$. Furthermore, we have $D_0\in {𝒟}^{\prime }$. By Lemma 11, there exists $p\in {\mathrm{\Gamma }}_{\delta }(D_0)$ such that $\mathrm{𝖽𝖾𝗉}(p,{𝒟}^{\prime })\ge (\frac{1}{2}-\epsilon )\cdot |{𝒟}^{\prime }|=(\frac{1}{2}-\epsilon )\cdot |{𝒟}^{\ast }|=(\frac{1}{2}-\epsilon )\cdot \mathrm{𝖽𝖾𝗉}(𝒟)$. This proves the corollary. $◀$

Using this corollary, we can reduce the task of maintaining a $(\frac{1}{2}-\epsilon )$-approximation of the maximum depth of disks to the dynamic discrete maximum-depth problem for disks. Let $𝒟$ be a dynamic set of disks. Corollary 12 implies that ${\max }_{p\in S}\mathrm{𝖽𝖾𝗉}(p,𝒟)\ge (\frac{1}{2}-\epsilon )\cdot \mathrm{𝖽𝖾𝗉}(𝒟)$, where $S={\mathrm{\Gamma }}_{\delta }(𝒟)$. Therefore, it suffices to consider the dynamic discrete maximum-depth instance with point set $S$ and disk set $𝒟$.