Dynamic Unit-Disk Range Reporting

To achieve our result in Lemma 7, roughly speaking, we can simply plug our shallow cutting algorithm for $\mathrm{\Gamma }$ in Theorem 8 and Lemma 9 into the algorithmic scheme of [6] or [10]. The algorithms of [6] and [10] are similar. For the method of [10], we can just replace their shallow cutting algorithm for lines [13] with our shallow cutting algorithm for $\mathrm{\Gamma }$ in Theorem 8 and replace their deletion-only data structure [24] with a combination of Lemmas 9 and 10. In addition, a general technique of querying multiple structures simultaneously from [6, Theorem 1] is also needed. For the method of [6], it was described for the plane problem in 3D with a query time $O({\log }^{2}n/\log \log n+k)$. We can follow the same algorithmic scheme but using our shallow cutting algorithm for $\mathrm{\Gamma }$ in Theorem 8 and Lemma 9 in the corresponding places. In addition, since our problem is a 2D problem, the technique of dynamic interval trees in [13] can be used to reduce the query time component from $O({\log }^{2}n/\log \log n)$ to $O(\log n)$. In the following, we adapt the method from Chan [10].

The data structure is an adaptation of the one for dynamic 3D convex hulls [9, 11, 23] (the idea was originally given in [9] and subsequent improvements were made in [11, 23]). We first give the following lemma. The lemma is similar to [10, Theorem 3.1], which is based on the result in [9], but Lemma 11 provides slightly better complexities than [10, Theorem 3.1] by using the recently improved result of [11] (see the full paper for more details).

With Lemma 11, we can answer a $k$-lowest-arcs query as follows. Consider a query vertical line ${\mathrm{\ell }}^{\ast }$. By Lemma 11(3), for each $j$, we compute the cell ${\mathrm{\Delta }}^j$ of $T_{i_k}^j$ intersecting ${\mathrm{\ell }}^{\ast }$, which takes $O(\log n)$ time by binary search as the $x$-projections of $T_{i_k}^j$ partition the $x$-axis into intervals. Then, we use “brute-force” to find the $k$ lowest arcs among all arcs in $L_{{\mathrm{\Delta }}^j}$ in $O(k)$ time as $|L_{{\mathrm{\Delta }}^j}|=O(k)$. Finally, among all arcs found above, we return the $k$ lowest arcs, which takes $O(k{\log }_{b}n)$ time. As such, the total query time is $O((\log n+k){\log }_{b}n)$.

We now improve the query time. We store each list $L_{\mathrm{\Delta }}$ by a deletion-only data structure that supports $k$-lowest-arcs queries. Suppose that such a deletion-only data structure is of space $S_0(|L_{\mathrm{\Delta }}|)$, supports each $k$-lowest-arcs query in $O(Q_0(|L_{\mathrm{\Delta }}|)+k)$ time and $D_0(|L_{\mathrm{\Delta }}|)$ deletion time, and can be built in $O(P_0(|L_{\mathrm{\Delta }}|))$ time. Then, by Lemma 11(2), each update causes at most $b^{O(1)}{\log }^{4}n$ amortized number of deletions to the lists $L_{\mathrm{\Delta }}$, and thus the amortized update time is

Note that the last term is obtained due to the following. After every $n$ updates, we reconstruct the entire data structure and thus the reconstruction time is on the order of ${\sum }_{\mathrm{\Delta }\in T_i^j}{P}_0(|L_{\mathrm{\Delta }}|)$, which is bounded by $P_0(b^{O(1)}n{\log }^{4}n)$ since ${\sum }_{\mathrm{\Delta }\in T_i^j}|L_{\mathrm{\Delta }}|=b^{O(1)}n{\log }^{4}n$ by Lemma 11(2) (assuming that $P_0(n)=\mathrm{\Omega }(n)$).

By Lemma 11(4), the total space is

For each query, there are two tasks: (1) Compute the cell ${\mathrm{\Delta }}^j$ for every $j$; (2) find the $k$ lowest arcs of all lists $L_{{\mathrm{\Delta }}^j}$ for all $j$. In the following, we solve the first task in $O(\log n+{\log }_{b}n)$ time and solve the second task in $O(\log n+k)$ time.

For the first task, following the method in [10], for each $i$, we use a dynamic interval tree [5] to store the intervals of the $x$-projections of the cuttings $T_i^j$ for all $j$ in an interval tree $T_i$. Using $T_i$, all $t$ intervals intersecting ${\mathrm{\ell }}^{\ast }$ can be computed in $O(\log n+t)$ time. In our problem, $t=O({\log }_{b}n)$. Insertions and deletions of intervals on $T_i$ can be supported in $O(\log n)$ amortized time. We can thus maintain all interval trees $T_i$ in additional amortized $\log n\cdot b^{O(1)}{\log }^{3}n$ time per update as the total size of all cuttings over time is $b^{O(1)}{\log }^{3}n$ by Lemma 11(1). This additional update time is subsumed by the first term in (1). In this way, the first task can be solved in $O(\log n+{\log }_{b}n)$ time.

For the second task, instead of brute-force, we use the deletion-only data structures for the lists $L_{{\mathrm{\Delta }}^j}$ and resort to a technique of querying multiple $k$-lowest-arcs data structures simultaneously in [6, Theorem 1], which is based on an adaption of the heap selection algorithm of Frederickson [22]. Applying [6, Theorem 1], the second task can be accomplished in $O(k+{\log }_{b}n\cdot {\max }_j{Q}_0(|L_{{\mathrm{\Delta }}^j}|))$ time, which is $O(k+{\log }_{b}n\cdot Q_0(O(k)))$ since the size of each $|L_{{\mathrm{\Delta }}^j}|$ is $O(k)$.

Combining the complexities of the first and second tasks, the overall query time is

Let $m=|L_{\mathrm{\Delta }}|$. Depending on $m$, we use different deletion-only data structures for $L_{\mathrm{\Delta }}$.

1. 1.

   If $m\ge {\log }^{3}n$, then we use Lemma 9 to handle $L_{\mathrm{\Delta }}$ with $P_0(m)=O(m\log m)$, $S_0(m)=O(m)$, $D_0(m)=O(\log m)$, $Q_0(m)=m^{1/2}{\log }^{O(1)}m$. Plugging them into (1), (2), and (3) and setting $b={\log }^{ϵ}n$, we obtain $U(n)=O({\log }^{5+ϵ}n)$, $S(n)=O(n\log n)$, and $Q(n)=O(\log n+k+k^{1/2}{\log }^{O(1)}k\cdot \log n/\log \log n)$. Since $m=O(k)$, we have $k=\mathrm{\Omega }(m)$. As $m\ge {\log }^{3}n$, we have $k=\mathrm{\Omega }({\log }^{3}n)$. Therefore, $Q(n)=O(\log n+k)$.

2. 2.

   If , then we use Lemma 10 to handle $L_{\mathrm{\Delta }}$ by setting $r=\log n/\log \log n$. This results in $P_0(m)=O(m\log m)$, $S_0(m)=O(m\log \log n)$, $D_0(m)=O(\log n\log m/\log \log n)$, $Q_0(m)=O(\log \log n+m\log \log n/\log n)$. Since , we have $D_0(m)=O(\log n)$. Plugging them into (1) and (3) and setting $b={\log }^{ϵ}n$, we obtain $U(n)=O({\log }^{5+ϵ}n)$ and $Q(n)=O(\log n+k+(\log \log n+k\log \log n/\log n)\cdot \log n/\log \log n)$, which is $O(\log n+k)$. For the space, since , if we plug $S_0(m)=O(m\log \log n)$ into (2), we only need to consider those $i$’s such that . There are only $O(\log \log n)$ such $i$’s. Therefore, we obtain $S(n)=O(n{\log }^2\log n)$ for all such $m$’s in this case.

Combining the above two cases leads to $U(n)=O({\log }^{5+ϵ}n)$, $S(n)=O(n\log n)$, and $Q(n)=O(\log n+k)$. We can actually obtain a better bound for the insertion time. If $P^{\prime }(n)$ is the preprocessing time for constructing the data structure for a set of $n$ arcs, then the amortized insertion time $I(n)$ is bounded by $I(n)=O(b{\log }_{b}n\cdot P^{\prime }(n)/n)$ [6, 11]. According to our above discussion and Lemma 11(4), constructing the deletion-only data structures for all lists $L_{\mathrm{\Delta }}$ is $O(n{\log }^{2}n)$. The shallow cuttings in Lemma 11 can be built in $O(n{\log }^{2}n)$ following the method in [11] and using our shallow cutting algorithm in Theorem 8. In this way, we can bound the amortized insertion time by $O(b{\log }_{b}n{\log }^{2}n)$, which is $O({\log }^{3+ϵ}n)$ with $b={\log }^{ϵ}n$. This proves Lemma 7.

Note that if a point $q\in Q$ whose $y$-coordinate is smaller than or equal to $-1$, then $q$ must be in $H_{\mathrm{\ell }}(Q)$ because every ${ℝ}^{+}$-constrained disk does not contain $q$ in the interior. Hence, in that case $q$ is irrelevant for computing $H_{\mathrm{\ell }}(Q)$ and thus can be ignored. If all points of $Q$ are irrelevant, then $H_{\mathrm{\ell }}(Q)$ is simply the region below the horizontal line whose $y$-coordinate is $-1$. In the following, we assume that every point of $Q$ is relevant.

Consider a point $q\in Q$. Let $a$ be a point on the $x$-axis $\mathrm{\ell }$ with such that $q$ is on the unit circle $C_a$ centered at $a$. Let $p$ be the lowest point of $C_a$. We define the left wing of $q$ to be the concatenation of the following two parts (see Fig. 3): (1) the arc of $C_a\cap R^{-}$ between $q$ and $p$, called the left wing arc, and the horizontal half-line with $p$ as the right endpoint, called the left wing half-line. The point $p$ is called the left wing vertex of $q$. We define the right wing of $q$ and the corresponding concepts symmetrically. The left and right wings together actually form the boundary of the line-separated $\alpha$-hull of $\{q\}$. In Fig. 1, the four (red) dotted arcs are wing arcs and the three (blue) dashed segments are on wing half-lines.

Consider two points $q,q^{\prime }\in {ℝ}^{-}$ such that . We say that $(q,q^{\prime })$ are in far-away position if holds, where $p$ is the right wing vertex of $q$ and $p^{\prime }$ is the left wing vertex of $q^{\prime }$ (see Fig. 3). In this case, $q^{\prime }$ is above the right wing of $q$ and there is no ${ℝ}^{+}$-constrained unit disk covering both $q$ and $q^{\prime }$. We use $\beta (q,q^{\prime })$ to denote the concatenation of the right wing arc of $q$, the segment $\overline{p{p}^{\prime }}$, and the left wing arc of $q^{\prime }$. In fact, the left wing of $q$, $\beta (q,q^{\prime })$, and the right wing of $q^{\prime }$ together form the boundary of the line-separated $\alpha$-hull of $\{q,q^{\prime }\}$. In Fig. 1, $q$ and $q^{\prime }$ are also in far-away position.

Define $Q_i=\{q_1,\mathrm{\dots },q_i\}$ for each $1\le i\le m$. Our algorithm handles the points of $Q$ incrementally from $q_1$ to $q_m$. For each $q_i$, the algorithm computes $H_{\mathrm{\ell }}(Q_i)$ by updating $H_{\mathrm{\ell }}(Q_{i-1})$ with $q_i$. Suppose that $q_{i_1},q_{i_2},\mathrm{\dots },q_{i_t}$ are the points of $Q_i$ that are the vertices of $H_{\mathrm{\ell }}(Q_i)$ sorted from left to right. Then, our algorithm maintains the following invariant: the boundary $\partial H_{\mathrm{\ell }}(Q_i)$ is $x$-monotone and consists of the following parts from left to right: the left wing of $q_{i_1}$, $\gamma (q_{i_j},q_{i_{j+1}})$ or $\beta (q_{i_j},q_{i_{j+1}})$, for each $j=1,2,\mathrm{\dots },t-1$ in order, and the right wing of $q_{i_t}$. $H_{\mathrm{\ell }}(Q_i)$ is the region below $\partial H_{\mathrm{\ell }}(Q_i)$.

Initially, for $q_1$, we set $\partial H_{\mathrm{\ell }}(Q_1)$ to the concatenation of the left wing and the right wing of $q_1$. In general, suppose we already have $\partial H_{\mathrm{\ell }}(Q_{i-1})$. We compute $\partial H_{\mathrm{\ell }}(Q_i)$ as follows. We process the points of $q_{i_1},q_{i_2},\mathrm{\dots },q_{i_t}$ in the backward order. For ease of exposition, we assume that $t>1$; the special case $t=1$ can be easily handled.

We first process the point $q_{i_t}$. If $q_{i_t}$ and $q_i$ are in the far-away position, then we delete the right wing of $q_{i_t}$ from $H_{\mathrm{\ell }}(Q_{i-1})$ and add $\beta (q_{i_t},q_i)$ and the right wing of $q_i$. This finishes computing $H_{\mathrm{\ell }}(Q_i)$. Below, we assume that $q_{i_t}$ and $q_i$ are not in the far-away position.

If $q_i$ is below the right wing of $q_{i_t}$, then $q_i$ is inside $H_{\mathrm{\ell }}(Q_{i-1})$. In this case, $H_{\mathrm{\ell }}(Q_i)$ is $H_{\mathrm{\ell }}(Q_{i-1})$ and we are done. If $q_i$ is above the right wing of $q_{i_t}$, then we further check whether the arc $\gamma (q_{i_t},q_i)$ exists (which is true if and only if there exists an ${ℝ}^{+}$-constrained unit disk covering both $q_{i_t}$ and $q_i$).

• $\mathrm{■}$

  If $\gamma (q_{i_t},q_i)$ does not exist (in this case $q_{i_t}$ must be below the left wing of $q_i$ and thus $q_{i_t}$ does not contribute to $H_{\mathrm{\ell }}(Q_i)$ because it is “dominated” by $q_i$), then we “prune” $q_{i_t}$ from $\partial H_{\mathrm{\ell }}(Q_{i-1})$, i.e., delete the right wing of $q_{i_t}$ and also delete $\gamma (q_{i_{t-1}},q_{i_t})$ or $\beta (q_{i_{t-1}},q_{i_t})$ whichever exists in $H_{\mathrm{\ell }}(Q_{i-1})$. Next, we process $q_{i_{t-1}}$ following the same algorithm.

• $\mathrm{■}$

  If $\gamma (q_{i_t},q_i)$ exists, then we further check whether $D$ contains $q_{i_{t-1}}$, where $D$ is the underlying disk of $\gamma (q_{i_t},q_i)$. If $q_{i_{t-1}}\in D$, then $q_{i_t}$ must be in $H_{\mathrm{\ell }}(\{q_{i_{t-1}},q_i\})$ and thus does not contribute to $H_{\mathrm{\ell }}(Q_i)$. In this case, we prune $q_{i_t}$ as above and continue processing $q_{i_{t-1}}$. If $q_{i_{t-1}}\notin D$, we delete the right wing of $q_{i_t}$ from $\partial H_{\mathrm{\ell }}(Q_{i-1})$ and add the arc $\gamma (q_{i_t},q_i)$ and the right wing of $q_i$; this finishes computing $H_{\mathrm{\ell }}(Q_i)$.

Clearly, the runtime for computing $H_{\mathrm{\ell }}(Q_i)$ is $O(1+t^{\prime })$, where $t^{\prime }$ is the number of points of $q_{i_1},q_{i_2},\mathrm{\dots },q_{i_t}$ pruned from $H_{\mathrm{\ell }}(Q_{i-1})$. The overall algorithm for computing $H_{\mathrm{\ell }}(Q)$ takes $O(m)$ time since once a point is pruned it will never appear on the hull again, which resembles Graham’s scan for computing convex hulls.