An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Recall that $u$ and $v$ have an edge if and only if $|uv|-r_u-r_v\le 0$. Notice that $|uv|-r_u-r_v\le 0$ holds if and only if $d_v(u)\le r_u$ or $d_u(v)\le r_v$. $◀$

By definition, $S_{i-1}$ has a site $u$ with $d_u(v)=d_{S_{i-1}}(v)$. If $d_{S_{i-1}}(v)\le r_v$, then $d_u(v)\le r_v$. By Observation 1, $G(S)$ has an edge connecting $u$ and $v$. As $u\in S_{i-1}$ and $v\in S\setminus S_{\le i-1}$, we obtain that $v\in S_i$.

If $v\in S_i$, then there is an edge in $G(S)$ connecting $v$ to a site $u\in S_{i-1}$. By Observation 1, $d_u(v)\le r_v$. It then follows that $d_{S_{i-1}}(v)\le d_u(v)\le r_v$. $◀$

We now prove that the algorithm is correct. Let $S_i^{\prime }$ be the set $S_i$ computed by our algorithm and let $S_i$ be the “correct” set of vertices at distance $i$ from $s$ in $G(S)$. Then, our goal is to prove that $S_i^{\prime }=S_i$ for all $i$. We do so by induction on $i$. Our base case is that $S_0^{\prime }=S_0$, which is obviously true because they are both $\{s\}$. Our inductive hypothesis is that $S_j^{\prime }=S_j$ for all . To prove that $S_i^{\prime }=S_i$, we will argue both $S_i^{\prime }\subseteq S_i$ and $S_i^{\prime }\supseteq S_i$.

First of all, since $S_j^{\prime }=S_j$ for all , our algorithm guarantees that every site of $S_i^{\prime }$ is at distance $i$ from $s$ in $G(S)$ and thus $S_i^{\prime }\subseteq S_i$. To see this, a site $v$ is added to $S_i^{\prime }$ in Line 11 because $d_{S_{i-1}}(v)\le r_v$. By Observation 2, $v\in S_i$.

We next prove that $S_i^{\prime }\supseteq S_i$. Consider a site $v\in S_i$. Our goal is to show that $v$ is also in $S_i^{\prime }$. We will prove in Lemma 3 that there exists a vertex $u\in S_{i-1}$ and a $u$-$v$ path $\pi$ in $𝒟𝒯(S)$ such that all internal vertices of $\pi$ are in $S_i$ (note that internal vertices refer to vertices of $\pi$ excluding $u$ and $v$). Let the vertices of $\pi$ be $u=w_0,w_1,\mathrm{\dots },w_k=v$. We argue that all $w_j$ with $1\le j\le k$ are added to $S_i^{\prime }$. To this end, because $w_j\in S_i$ for all $1\le j\le k$, it is sufficient to argue that $w_j$ is added to $Q$ because when $w_j$ is popped from $Q$, it will pass the check on Line 10 by Observation 2 and then be added to $S_i^{\prime }$. Indeed, $w_1$ is added to $Q$ on Line 7 because $w_1\in N_{𝒟𝒯}(u)$. Since $w_2\in N_{𝒟𝒯}(w_1)$, $w_2$ will be added to $Q$ on Line 12 no later than right after $w_1$ is added to $S_i^{\prime }$ on Line 11. Following the same argument, $w_3,w_4,\mathrm{\dots },w_k=v$ will all be added to $Q$ and thus added to $S_i^{\prime }$ as well. This proves that $v\in S_i^{\prime }$. Therefore, $S_i^{\prime }\supseteq S_i$.

In summary, we have proved $S_i^{\prime }=S_i$ and thus the correctness of the algorithm.

We extend the proof of [6, Lemma 1] for the unit-disk graph case to our general disk graph problem.

Let $u={\beta }_v(S_{i-1})$, i.e., $u$ is a nearest neighbor of $v$ in $S_{i-1}$. Consider the line segment $\overline{uv}$ and the sites whose Voronoi regions in $𝒱𝒟(S)$ intersect $\overline{uv}$. Let $w_0,w_1,\mathrm{\dots },w_k$ be these sites in the order that their Voronoi regions intersect $\overline{uv}$ with $w_0=u$ and $w_k=v$. Note that repetitions are possible, so it could be that $w_j=w_{j^{\prime }}$ for $j\ne j^{\prime }$. See Figure 1 for an example. For ease of discussion, we assume that $\overline{uv}$ does not contain any Voronoi vertices of $𝒱𝒟(S)$ (otherwise, we could replace $v$ by a point arbitrarily close to $v$ and then follow the same argument). This implies that, for every $0\le j\le k-1$, $\overline{uv}$ crosses the Voronoi edge between $w_j$ and $w_{j+1}$. This further implies that $w_j$ and $w_{j+1}$ are adjacent in $𝒟𝒯(S)$, so $\pi =w_0,w_1,\mathrm{\dots },w_k$ is a $u$-$v$ path in $𝒟𝒯(S)$.

Next, we need to show that all internal vertices $w_j$ ($1\le j\le k-1$) of $\pi$ are in $S_i$. We will first prove that there is an edge $(u,w_j)$ in $G(S)$ connecting $u$ and $w_j$, meaning that $w_j\in S_{i-2}\cup S_{i-1}\cup S_i$ since $u\in S_{i-1}$. Then, we will show that $w_j\notin S_{i-2}\cup S_{i-1}$, so $w_j\in S_i$ must hold. This will complete the proof of the lemma.

We first argue that $G(S)$ has an edge $(u,v)$. Indeed, since $v\in S_i$, there is a vertex $u^{\prime }\in S_{i-1}$ connecting to $v$ by an edge in $G(S)$. By Observation 1, $d_{u^{\prime }}(v)\le r_v$. Since $u={\beta }_v(S_{i-1})$, we have $d_u(v)\le d_{u^{\prime }}(v)\le r_v$. By Observation 1, $G(S)$ has an edge $(u,v)$.

Consider any $w_j$ with $1\le j\le k-1$. We now argue that $G(S)$ has an edge $(u,w_j)$. Recall that $\overline{uv}$ intersects $\text{Vor}(w_j)$. Let $p$ be a point of $\overline{uv}\cap \text{Vor}(w_j)$; see Figure 2. We can derive the following:

where (1) is due to the triangle inequality, (2) is due to $p\in \text{Vor}(w_j)$ (therefore, $|w_{j}p|-r_{w_j}=d_{w_j}(p)\le d_v(p)=|vp|-r_v$), (3) is due to $p\in \overline{uv}$, and (4) is due to Observation 1 and the fact that $G(S)$ has an edge $(u,v)$. Consequently, by Observation 1, $G(S)$ has an edge $(u,w_j)$.

To prove that $w_j\notin S_{i-2}\cup S_{i-1}$, $1\le j\le k-1$, as before, we pick a point $p\in \overline{uv}\cap \text{Vor}(w_j)$ and derive the following:

where (1) is due to the triangle inequality and our general position assumption (because $p\in \overline{uv}$, equality occurs only if $u$, $v$, and $w_j$ are collinear, violating our general position assumption), (2) is due to $p\in \text{Vor}(w_j)$ (therefore, $|w_{j}p|-r_{w_j}=d_{w_j}(p)\le d_u(p)=|up|-r_u$), (3) is due to $p\in \overline{uv}$, and (4) is due to Observation 1 and the fact that $G(S)$ has an edge $(u,v)$, as proven above.

Notice that $w_j\notin S_{i-1}$ since otherwise proved above would contradict with $u={\beta }_v(S_{i-1})$. Also, since $G(S)$ has an edge $(w_j,v)$ and $v\in S_i$, $w_j$ cannot be in $S_{i-2}$ (since otherwise $v$ would be in $S_{\le i-1}$, contradicting with that $v\in S_i$). This proves that $w_j\notin S_{i-2}\cup S_{i-1}$. $◀$

The following theorem summarizes our result.

In the $L_{\mathrm{\infty }}$ metric, each disk becomes a square centered at a site of $S$. For this case, an $O(n\log n)$-time algorithm was given by Klost [18] to solve the SSSP problem, which uses the involved techniques in [3]. We can solve this problem in $O(n\log n)$ time in a much simpler way by making the following changes to Algorithm 1. First, use the $L_{\mathrm{\infty }}$ metric to measure the distance $|pq|$ of any two points $p,q$ in the plane. Second, use additively-weighted Voronoi diagrams in the $L_{\mathrm{\infty }}$ metric instead. Note that constructing an additively-weighted Voronoi diagram for a set of $n$ points in the $L_{\mathrm{\infty }}$ metric is equivalent to constructing a Voronoi diagram for a set of $n$ squares in the $L_{\mathrm{\infty }}$ metric. This latter problem can be solved in $O(n\log n)$ time, e.g., by the algorithm of Papadopoulou and Lee [21]. As such, Algorithm 1 can be modified to solve the $L_{\mathrm{\infty }}$ metric case in $O(n\log n)$ time. The algorithm is much simpler than the one in [18]. The $L_1$ case can be treated analogously.