Single-Source Shortest Path Problem in Weighted Disk Graphs

Let $uv$ be an edge of $G$ with $r_u\le r_v$. We call $uv$ a regular edge if , and an irregular edge if $\frac{r_v}{r_u}\ge 2$. We can identify all edges of $G$ efficiently by using ${⊞}_c$, $P_{\text{mid}}(c)$ and $P_{\text{small}}(c)$.

We utilize the strategic adaptation of Dijkstra’s algorithm in a cell-by-cell manner with $P_{\text{small}}(\cdot )$ and $P_{\text{mid}}(\cdot )$. This strategy was used in [20] to design an efficient algorithm for the weighted SSSP problem on unit disk graphs. For concreteness, we describe the details of the strategy below. Let $v$ be the vertex with the smallest dist-value among all vertices not processed so far. As an invariant, we shall guarantee that all vertices of $G$ which have been processed have correct dist-values, and $v$ has a correct dist-value if its predecessor in the shortest $s$-$v$ path has been processed. We want to process not only $v$ but also all vertices in $P_{\text{mid}}(c_v)$ simultaneously. However, notice that, at this moment, the vertices in $P_{\text{mid}}(c_v)$ do not necessarily have correct dist-values.

Thus, as a first step, we compute the correct dist-values for all vertices in $P_{\text{mid}}(c_v)$. If the predecessor $w$ of a vertex $v^{\prime }\in P_{\text{mid}}(c_v)$ in the shortest $s$-$v^{\prime }$ path already has the correct dist-value, we can simply update the dist-values of $P_{\text{mid}}(c_v)$ by considering all edges whose one endpoint is in $P_{\text{mid}}(c_v)$. However, it is possible that $w$ has not been processed yet so far and does not have the correct dist-value. Fortunately, even in this case, we can show that $w$ has a correct dist-value. To see this, let $u$ be the predecessor of $w$ in the shortest $s$-$w$ path. Then $u{v}^{\prime }$ cannot be an edge of the graph since otherwise $u$ is the predecessor of $v^{\prime }$ in the shortest $s$-$v^{\prime }$ path. Therefore, $|u{v}^{\prime }|>r_{v^{\prime }}$. As $v,v^{\prime }\in P_{\text{mid}}(c_v)$, $|u{v}^{\prime }|>r_{v^{\prime }}>|v{v}^{\prime }|$. Hence, . The last inequality follows since the concatenation of $v{v}^{\prime }$ and the shortest $s$-$v$ path is longer than the shortest $s$-$v^{\prime }$ path. Now $u$ must have been processed since $v$ is the vertex with the smallest dist-value among all vertices not processed so far. Due to the invariant, $w$ must have the correct dist-value. Consequently, we can update the dist-values of all vertices of $P_{\text{mid}}(c_v)$ by applying $\text{Update}(N(c_v),P_{\text{mid}}(c_v))$ where $N(c_v)$ denotes the set of neighbors of $P_{\text{mid}}(c_v)$ in $G$.

The second step is to transmit the correct dist-values of $P_{\text{mid}}(c_v)$ into their neighbors in order to satisfy the second invariant. Lastly, we remove $P_{\text{mid}}(c_v)$ from the graph.

The complexity of this strategy primarily depends on the cost of searching all neighbors of $P_{\text{mid}}(c_v)$. This was not a big deal in [20], as in a unit disk graph, each cell interacts with only a constant number of other cells. In the case of disk graphs, however, a vertex with radius $\mathrm{\Theta }(\mathrm{\Psi })$ can be adjacent to vertices in $P_{\text{mid}}(c)$ for $O({\mathrm{\Psi }}^2)$ distinct grid cells $c$. To avoid polynomial dependency on $\mathrm{\Psi }$, we handle regular edges and irregular edges separately. More specifically, we can search all regular edges by considering $P_{\text{mid}}(c)$ for all $c\in {⊞}_{c_v}$ by Lemma 1. Since ${⊞}_{c_v}$ consists of $O(1)$ cells, we can avoid the polynomial dependency on $\mathrm{\Psi }$ through the appropriate use of the Update subroutine.

However, the same approach cannot be used to search all irregular edges as up to $\mathrm{\Theta }({\mathrm{\Psi }}^2)$ sets of $P_{\text{mid}}(\cdot )$ may interact with $P_{\text{mid}}(c_v)$ in the worst case. We address this issue with a novel approach, which we call lazy update scheme. We say $w$ is a small neighbor of a vertex $u$ if $uw$ is an irregular edge and $r_u>r_w$. Furthermore, we say $w$ is a small neighbor of a cell $c$ if there is a vertex $u\in P_{\text{mid}}(c)$ forming an irregular edge with $w$ and $r_u>r_w$. In the basic strategy, we transmit the correct dist-value of $v$ to all neighbors whenever we process $v$. In the lazy update scheme, we postpone the transmission to $P_{\text{mid}}(c)$ for all cells $c$ such that $v$ is a small neighbor of $c$. We handle several postponed update requests at once at some point. More specifically, let $V_x$ be the set of small neighbors of $c$ whose dist-values are in the range $[x,x+2|c|]$. We transmit the dist-values of $V_x$ into $P_{\text{mid}}(c)$ right after all vertices of $V_x$ have been processed. Due to the following lemma, we can bound the number of lazy updates into $O(1)$ for each cell $c$, and this enables us to avoid the polynomial dependency on $\mathrm{\Psi }$.

However, this may cause an inconsistency issue during the first step. When we process the vertices of $P_{\text{mid}}(c_v)$, now the first update does not transmit the dist-values of the small neighbors of $c_v$. If a predecessor $w$ of $v^{\prime }\in P_{\text{mid}}(c_v)$ in the shortest $s$-$v^{\prime }$ path is a small neighbor of $v^{\prime }$, it is possible that the lazy update has not occurred even though $w$ has already been processed. We show that this cannot happen using the following geometric lemma.

By this lemma, . Subsequently, roughly speaking, the lazy update that transmits dist-values of $w$ into $v^{\prime }$ occurs in advance when we process the vertices of $P_{\text{mid}}(c_{v^{\prime }})$.

We compute $d(v)$ for all $v\in P$ adjacent to $s$ in $G$ and set $\text{dist}(v)$ to $|sv|$. Furthermore, for each grid cell $c$, let $\overline{L}(c)$ be the set of grid cells $c^{\prime }$ where $P_{\text{mid}}(c)$ contains a small neighbor of $c^{\prime }$. For technical reasons, we compute a superset $L(c)$ of $\overline{L}(c)$ which contains all cells $c^{\prime }$ with such that there is an edge between a vertex of $P_{\text{mid}}(c)$ and a vertex of $P_{\text{mid}}(c^{\prime })$. Furthermore, we set $L(c_s)$ as an empty set where $c_s$ is the grid cell such that the source $s$ is contained in $P_{\text{mid}}(c_s)$. We will use the information of $L(c)$ to deal with the lazy update. Then the algorithm consists of several rounds. In each round, we check $\text{dist}(v)$ for all $v\in R$ and $\text{alarm}(c)$ for all $c\in \mathrm{\Gamma }$. Subsequently, we find the minimum value $k$ among these values, and proceed depending on the type of $k$. The algorithm terminates when $R$ becomes empty. We utilize Update$(U,V)$ subroutine for both cases.

Intuitively, if $u\in U$ has correct dist-values and $u$ is the predecessor of $v\in V$ in the shortest $s$-$t$ path, then all such $v$ gets the correct dist-values after the subroutine Update$(U,V)$. The rest of this section is devoted to giving detailed instructions on case studies of $k$.

In this case, we first apply the subroutine $\text{Update}({\bigcup }_{c\in {⊞}_{c_v}}{P}_{\text{mid}}(c),P_{\text{mid}}(c_v))$. Interestingly, we will see later that after this, all vertices in $P_{\text{mid}}(c_v)$ have the correct dist-values. Then using the correct dist-values of $P_{\text{mid}}(c_v)$, we update the dist-values of the neighbors of the vertices in $P_{\text{mid}}(c_v)$. This is done by applying $\text{Update}(P_{\text{mid}}(c_v),{\bigcup }_{c\in {⊞}_{c_v}}{P}_{\text{mid}}(c)\cup P_{\text{small}}(c))$ and setting $\text{alarm}(c)=\text{dist}(v)+2|c|$ for all $c\in L(c_v)$ with $\text{alarm}(c)=\mathrm{\infty }$, where the former takes care of the neighbors of the vertices in $P_{\text{mid}}(c_v)$ connected by regular edges and the small neighbors of $c_v$, and the latter takes care of the other neighbors. Finally, we remove $P_{\text{mid}}(c_v)$ from $R$.

In this case, we shall correct the dist-values of all $v\in P_{\text{mid}}(c)$ such that the predecessor of $v$ is a small neighbor of $v$. This is done by applying $\text{Update}({\bigcup }_{c^{\prime }\in {⊞}_c}{P}_{\text{small}}(c^{\prime }),P_{\text{mid}}(c))$. After this, we reset $\text{alarm}(c)$ to $\mathrm{\infty }$.

We apply induction on the index $i$ of the round. For the base case, the first round of the algorithm is a round of Case 1 of $k=\text{dist}(s)$, where $s$ is a source vertex. The shortest $s$-$u$ path with $u\in P_{\text{mid}}(c_s)$ is $su$ and $\text{dist}(u)=d(u)$ due to the pre-processing.

Now we assume that Lemma 6 holds up to the $(i-1)$-th round. Suppose the $i$-th round performs line 5. First we show (1). Let $x$ be the closest vertex to $v$ along the shortest $s$-$v$ path such that $d(x)=\text{dist}(x)$. Note that $x\ne s$ because all children of $s$ have correct-dist values due to the pre-processing. If $x=v$, we are done. Otherwise, $x\notin R$ since . Then by induction hypothesis on the round which removes $x$ from $R$, a child $y$ of $x$ satisfies $d(y)=\text{dist}(y)$ unless $x$ is a small neighbor of $y$. If $x$ is a small neighbor of $y$, $\text{alarm}(c_y)$ was at most $d(x)+2|c_y|$ after that round. Since $y\in P_{\text{mid}}(c_y)$, $8|c_y|\le r_y$. Hence, due to Corollary 5. Thus, $d(y)=\text{dist}(y)$ by induction hypothesis (3) on the round of $k=\text{alarm}(c_y)$. This contradicts the choice of $x$.

Next we show (2). We may assume $u$ is not a source vertex $s$. Let $w=\text{prev}(u)$. We show that $d(w)=\text{dist}(w)$. If $w=s$ or $ws$ is an edge of $G$, we are done by the preprocessing. Hence, we may assume that $x:=\text{prev}(w)$ exists and $x$ is not a source vertex $s$. Note that the proof of (1) implicitly says that for any vertex $v^{\prime }$ with $d(v^{\prime })\le k$, $d(v^{\prime })=\text{dist}(v^{\prime })$ at the onset of line 5. Hence, we are enough to consider the case that $d(w)>d(v)$. Notice that $xu$ is not an edge of $G$ since otherwise, $x$ is the predecessor of $u$. Then , where the last inequality comes from $u,v\in P_{\text{mid}}(c_v)$. Hence, $d(x)=\text{dist}(x)$ and therefore $x\notin R$ due to the choice of $v$. Thus, by induction hypothesis on the round which removes $x$ from $R$, $d(w)=\text{dist}(w)$ unless $x$ is a small neighbor of $w$ and . If $x$ is a small neighbor of $w$, $\text{alarm}(c_w)$ is set to at most $d(x)+2|c_w|$ after that round. After a similar computation as we did in (1), we can derive using the facts that and Corollary 5. Now $d(w)=\text{dist}(w)$ due to induction hypothesis (3).

Hence, for all cases, $d(w)=\text{dist}(w)$. Since $u$ is not a leaf on the shortest path tree, $|wu|\ge \frac{1}{2}{r}_u$ due to Corollary 5. The only problematic case occurs when $w$ is a small neighbor of $u$ and the lazy update from $w$ to $P_{\text{mid}}(c_u)$ has not occurred. In this case, $d(w)+2|c_u|>d(v)$ due to induction hypothesis (3). Then leads to a contradiction. Finally, (3) is followed by (2) and the fact that $\text{prev}(u)\notin R$ due to the choice of $k$. $◀$

In the pre-processing step, we compute $\text{dist}(v)$ for all neighbors $v$ of $s$, and $L(c)$ for all grid cells $c$. Here, $L(c)$ denotes the set of cells $c^{\prime }$ such that $P_{\text{mid}}(c)$ contains a small neighbor of $c^{\prime }$. The former part takes $O(n)$ time by checking $|sv|-r_s-r_v$ for all $v\in P$. We do not use the floor function on the real RAM model to implement the hierarchical grid.

Let $n_i$ be the number of vertices involved in $P_{\text{mid}}(c_v)\cup {\bigcup }_{c\in {⊞}_{c_v}}(P_{\text{mid}}(c)\cup P_{\text{small}}(c))$ in the $i$-th round of line 5-6. If $i$-th round is a round of Case 2, we set $n_i$ to 0. The time complexity of this part is then ${\mathrm{\Sigma }}_{i}O(n_i{\log }^{2}n)$. We show that each $P_{\text{mid}}(c)$ and $P_{\text{small}}(c)$ appears in $O(1)$ rounds. First, since we remove $P_{\text{mid}}(c_v)$ from $R$ after the round $k=\text{dist}(v)$, each $P_{\text{mid}}(c)$ appears exactly once in the term $P_{\text{mid}}(c_v)$. Suppose $c\in {⊞}_{c^{\prime }}$. Then $c$ is contained in axis-parallel square of diameter $64|c^{\prime }|$ centered at $p(c)$ and $|c|\le 2|c^{\prime }|$. Conversely, $c^{\prime }$ is contained in the axis-parallel square of diameter $65|c|$ centered at $p(c)$. Therefore, the number of different $c^{\prime }$ with $c\in {⊞}_{c^{\prime }}$ is $O(1)$ for a fixed $c$. Hence, each $P_{\text{mid}}(c)$ and $P_{\text{small}}(c)$ appears $O(1)$ rounds through the term ${\bigcup }_{c\in {⊞}_{c_v}}(P_{\text{mid}}(c)\cup P_{\text{small}}(c))$. Note that each vertex $v$ is contained in one $P_{\text{mid}}(c)$ and $O(\log \mathrm{\Psi })$ $P_{\text{small}}(c)$ for $c\in \mathrm{\Gamma }$. Thus,

Let $n_i^{\prime }$ be the number of vertices involved in $P_{\text{mid}}(c)\cup {\bigcup }_{c^{\prime }\in {⊞}_c}(P_{\text{small}}(c^{\prime }))$ in the $i$-th round of line 12. If $i$-th round runs a round of Case 1, we set $n_i^{\prime }$ to 0. The time complexity of this part is then ${\mathrm{\Sigma }}_{i}O(n_i^{\prime }{\log }^{2}n)$. Since $\text{alarm}(c)$ always set to $d(v)+2|c|$ for some $v\in P$ and by Lemma 3, each cell $c$ is referenced by line 11 $O(1)$ times. Again, there are $O(1)$ grid cells $c^{\prime }$ such that ${⊞}_{c^{\prime }}$ contains a fixed cell $c$, and each $v$ is contained in one $P_{\text{mid}}(c)$ and $O(\log \mathrm{\Psi })$ $P_{\text{small}}(c)$ sets. Thus, the total time complexity is

We maintain two priority queues, one of which stores vertex $v\in R$ with priority $\text{dist}(v)$, and the other queue stores cell $c\in \mathrm{\Gamma }$ with priority $\text{alarm}(c)$. Once the algorithm performs line 3, we peek an element with minimum priority for each queue, and then choose $k$ as the minimum value among them. The total cost of the queue operations is dominated by the total cost caused by $\text{Update}$ subroutines.

For an integer $i\ge 0$, let ${\mathrm{\Gamma }}_i$ be a grid of level $i$, which consists of axis-parallel square cells of diameter $2^i$. Among all grid cells of ${\bigcup }_i{\mathrm{\Gamma }}_i$, let $c$ be the grid cell of the smallest level that contains $P$. A compressed quadtree $𝒬$ is a rooted tree defined as follows. We start from $c$ as the root of the tree and iteratively expand the tree. More specifically, whenever we process $c\in {\mathrm{\Gamma }}_i$, we stop the expansion if $c$ contains exactly one point of $P$. Otherwise, we compute at most four cells of ${\mathrm{\Gamma }}_{i-1}$ that are nested in $c$, and contain at least one point of $P$. If there is exactly one such child $c^{\prime }$, we remove $c$ and connect $c^{\prime }$ to the parent node of $c$. Then we move on to children of $c$.

For our purpose, the compressed quadtree is extended to contain all grid cells of ${⊞}_{c_v}$ for all $v\in P$. It also takes an $O(n\log n)$ time to compute the extended tree [2].

As the height of $𝒬$ is $O(n)$, the direct use of Algorithm 2 is expensive: each vertex may be contained in $\mathrm{\Theta }(n)$ grid cells, which was $O(\log \mathrm{\Psi })$ in Section 2. Our goal is to compute a path system in $𝒬$ such that every root-node path of $𝒬$ can be represented by the concatenation of $O(\log n)$ paths in the path system. We say an edge $c{c}^{\prime }\in 𝒬$ is heavy if $c^{\prime }$ is the first child of $c$ in the order of children, where we give an order by the total number of nodes in the subtree rooted at $c^{\prime }$ among all children of $c$. We say $c{c}^{\prime }$ light otherwise. A heavy path of $𝒬$ is the maximal path on $𝒬$ that consists of only heavy edges. The heavy path decomposition is the collection of all heavy paths in $𝒬$.

Then we use the approach of [2] as a black box. That is, we define a set $\mathrm{\Pi }$ of $O(n)$ canonical paths, such that every root-node path of $𝒬$ can be uniquely represented by the concatenation of $O(\log n)$ disjoint canonical paths. Also, each canonical path is a subpath of a heavy path, and each node of $𝒬$ is contained in $O(\log n)$ canonical paths. We can compute $\mathrm{\Pi }$ in $O(n\log n)$ time using standard data structures. See [2] for details.

We primarily follow the notion of a proxy graph as presented in [2, 15], with slight modifications to the notation for our purpose. For an irregular edge $uv$ with , we call $u$ a small neighbor of $v$, and $v$ a large-neighbor of $u$. For a canonical path $\pi$, we use $c_{\pi }$ to denote the lowest cell of $\pi$. Also, we use $|{\pi }_{\mathrm{\ell }}|(=|c_{\pi }|)$ and $|{\pi }_t|$ to denote the diameter of the lowest cell and the topmost cell of $\pi$, respectively. We then define a set ${𝒞}_{\pi }$ of $\alpha$ congruent cones of radius $3h|{\pi }_t|$, all sharing the same apex at $p(c_{\pi })$. Let $\mathrm{\Lambda }$ be the set of all pairs $(c_{\pi },C)$ for all canonical paths $\pi$ and all cones $C\in {𝒞}_{\pi }$. See Figure 2(a-b).

We say an irregular edge $uv$ is redundant if . Due to Lemma 4, if a redundant edge $uv$ appears on the shortest path tree, then one endpoint, say $u$, is a leaf on the tree. Therefore, we can postpone the correction of $\text{dist}(u)$ until the last, as no shortest $s$-$w(\ne u)$ path intersects $u$. In fact, our algorithm handles these edges during post-processing.

For a pair $\lambda =(c,C)\in \mathrm{\Lambda }$, let $r(C)$ be the radius of $C$. For a vertex $v\in P$, recall that $c_v$ is a grid cell such that $v\in P_{\text{mid}}(c_v)$. Let ${\overline{c}}_v$ be the smallest grid cell on the root-$c_v$ path in $𝒬$ whose diameter is at least $h|c_v|$. We let ${\mathrm{\Pi }}_v$ be the set of $O(\log n)$ consecutive canonical paths representing the root-${\overline{c}}_v$ path. We define three subsets of $P$ with respect to $\lambda$. Here, $p(c)$ is the center point of $c$.

Intuitively, for any irregular edge $uv$, some $\lambda$ encodes $uv$ as $u\in P_{\text{small}}(\lambda )$ and $v\in P_{\text{large}}(\lambda )\cup P_{\text{post}}(\lambda )$. Moreover, $v\in P_{\text{large}}(\lambda )$ if $uv$ is a non-redundant. Later, our algorithm runs Dijkstra’s algorithm in a cell-by-cell manner w.r.t. $P_{\text{mid}}(\cdot ),P_{\text{small}}(\cdot ),$ and $P_{\text{large}}(\cdot )$.

Recall that Algorithm 2 updates small neighbors of $v$ once it corrects the dist-values of $P_{\text{mid}}(c_v)$, whereas it postpones the update to (informal) large neighbors of $v$. In this section, we apply the lazy update scheme for both large and small neighbors of $v$. The main reason is as follows. Due to Lemma 6-(2), all vertices of $P_{\text{mid}}(c_v)$ simultaneously get correct dist-values after the call of line 5. This property heavily relies on the geometric property of $P_{\text{mid}}(c_v)$ such that for any $u,w\in P_{\text{mid}}(c_v)$, $|uw|\le \frac{1}{8}{r}_u$. However, this property no longer holds for $P_{\text{large}}(\lambda )$. More specifically, once we handle $v\in P_{\text{large}}(\lambda )$, there might be a vertex $u\in P_{\text{large}}(\lambda )$ whose predecessor in the shortest $s$-$u$ has not been processed, and therefore, we cannot get correct dist-values of $P_{\text{large}}(\lambda )$ at this point.

Hence, one might consider a lazy update scheme to resolve this issue: delay the transmission of dist-values of $P_{\text{large}}(\lambda )$ in the range $[x,x+f(\lambda )]$ for some function $f$ of $\lambda$ until all dist-values smaller than $x+f(\lambda )$ have been processed. Unfortunately, this naive approach itself is not useful. Recall that for $v\in P_{\text{large}}(\lambda )$ with $\lambda =(c,C)$, $r_v$ is in range $[h|c|,\frac{2}{3}r(C)]$ and $r(C)/|c|$ can be very large. Hence, we cannot partition the dist-values of $P_{\text{large}}(\lambda )$ into a constant number of ranges $[x,x+f(\lambda )]$, and the number of updates from $P_{\text{large}}(\lambda )$ to $P_{\text{small}}(\lambda )$ might be $\mathrm{\Theta }(n)$, which leads to quadratic running time in total. We reduce the running time using the following geometric observation. See also Figure 3. Let $\lambda =(c,C)$.

Suppose we know the subset $P(\lambda )$ of $P_{\text{large}}(\lambda )$ whose dist-values have been corrected, and our algorithm will transmit dist-values of $P(\lambda )$ to $P_{\text{small}}(\lambda )$ right after all dist-values smaller than $d(v)+r_v-6|c|$ have been processed for some $v\in P(\lambda )$. Then, Lemma 20 guarantees that $P(\lambda )$ contains all vertices of $P_{\text{large}}(\lambda )$ whose radii are smaller than $r_v$. Furthermore, after the lazy update, all vertices of $P_{\text{small}}(\lambda )$ adjacent to $u\in P_{\text{large}}(\lambda )$ with $r_u\le r_v$ will have correct dist-values. Hence, the following procedure works.

• $\mathrm{■}$

  Step 1. Maintain a priority queue that stores $v\in P(\lambda )$ with priority $d(v)+r_v-6|c|$.

• $\mathrm{■}$

  Step 2. Once we handle the lazy update caused by $d(v)+r_v-6|c|$, we update dist-values of the vertices of $P_{\text{small}}(\lambda )$ which are adjacent to a vertex $v^{\prime }\in P(\lambda )$ with $r_{v^{\prime }}\le r_v$.

• $\mathrm{■}$

  Step 3. After the update, we remove the updated vertices from $P_{\text{small}}(\lambda )$.

Recall that the running time of $\text{Update}(U,V)$ is $O((|U|+|V|){\log }^{2}n)$ time. Although there might $\mathrm{\Theta }(n)$ calls of Update for $(P_{\text{large}}(\lambda ),P_{\text{small}}(\lambda ))$, the total size of $|V|$ can be bounded by $\tilde{O}(n)$ due to Step 3 and Lemma 19. Notice that $U$ always corresponds to a subset $P(\lambda )$ of $P_{\text{large}}(\lambda )$, which starts as an empty set and grows as the algorithm progresses. Hence, we implement incremental data structures with near-linear construction time by carefully dynamizing Update subroutine, inspired by the spirit of [3].

We introduced an incremental data structure to handle the $\mathrm{\Theta }(n)$ updates from $P_{\text{large}}(\lambda )$ to $P_{\text{small}}(\lambda )$. However, due to a similar reason, the number of lazy updates from $P_{\text{small}}(\lambda )$ to $P_{\text{large}}(\lambda )$ might be $\mathrm{\Theta }(n)$. Fortunately, we can implement this direction of lazy update using solely Update subroutine carefully.