# Reachability Problems for Transmission Graphs

Shinwoo An Pohang University of Science and Technology, Korea. Email:
{shinwooan<EMAIL_ADDRESS>Eunjin Oh11footnotemark: 1

###### Abstract

Let $P$ be a set of $n$ points in the plane where each point $p$ of $P$ is
associated with a radius $r_{p}>0$. The transmission graph $G=(P,E)$ of $P$ is
defined as the directed graph such that $E$ contains an edge from $p$ to $q$
if and only if $|pq|\leq r_{p}$ for any two points $p$ and $q$ in $P$, where
$|pq|$ denotes the Euclidean distance between $p$ and $q$. In this paper, we
present a data structure of size $O(n^{5/3})$ such that for any two points in
$P$, we can check in $O(n^{2/3})$ time if there is a path in $G$ between the
two points. This is the first data structure for answering reachability
queries whose performance depends only on $n$ but not on the number of edges.

##  1 Introduction

Consider a set $S$ of unit disks in the plane. The _intersection graph_ for
$S$ is defined as the undirected graph whose vertices correspond to the disks
in $S$ such that two vertices are connected by an edge if and only if the two
disks corresponding to them intersect. It can be used as a model for broadcast
networks: The disks of $S$ represent transmitter-receiver stations with the
same transmission power. One can view the broadcast range of a transmitter as
a unit disk.

One straightforward way to deal with the intersection graph for $S$ is to
construct the intersection graph explicitly, and then run algorithms designed
for general graphs. However, the intersection graph for $S$ has complexity
$\Theta(n^{2})$ in the worst case even though it can be (implicitly)
represented as $n$ disks. Therefore, it is natural to seek faster algorithms
for an intersection graph implicitly represented as its underlying set of
disks. For instance, the shortest path between two vertices in a unit-disk
intersection graph can be computed in near linear time [21]. For more
examples, refer to [3, 5, 12].

A _transmission graph_ is a _directed_ intersection graph, which is introduced
to model broadcast networks in the case that transmitter-receiver stations
have different transmission power [18, 20]. Let $P$ be a set of $n$ points in
the plane where each point $p$ of $P$ is associated with a radius $r_{p}>0$.
The _transmission graph_ $G=(V,E)$ of $P$ is an weighted directed graph whose
vertex set corresponds to $P$. There is an edge ${(p,q)}$ in $E$ for two
points $p$ and $q$ in $P$ if and only if the Euclidean distance $|pq|$ between
$p$ and $q$ is at most $r_{p}$. The weight of an edge ${(p,q)}$ is defined as
$|pq|$. It is sometimes convenient to consider a point $p$ of $P$ as the disk
of radius $r_{p}$ centered at $p$. We call it the _associated disk_ of $p$,
and denote it by $D_{p}$. We say $p$ is _reachable_ to $q$ if there is a
$p$-$q$ path in $G$.

In this paper, we consider the _reachability_ problem for transmission graphs:
Given a set $P$ of points associated with radii, check if a point of $P$ is
reachable to another point of $P$ in the transmission graph. In the context of
broadcast networks, this problem asks if a transmission station can transmit
information to a receiver. We consider three versions of the reachability
problem: the single-source reachability problem, (discrete) reachability
oracles, and continuous reachability oracles. The _single-source reachability
problem_ asks to compute all vertices reachable from a given source node $p\in
P$ in the transmission graph of $P$. Indeed, we consider the more general
problem that asks to compute a $t$-spanner of size $O(n)$. Once we have a
$t$-spanner of size $O(n)$, we can compute all vertices reachable from a given
source node in linear time. A _(discrete) reachability oracle_ is a data
structure for $P$ so that, given any two query points $p$ and $q$ in $P$, we
can check if $p$ is reachable to $q$ in $G$ efficiently. A _continuous
reachability oracle_ is a data structure for $P$ for answering reachability
queries that takes two points in the plane, one in $P$ and one not necessarily
in $P$, as a query.

###  1.1 Previous Work.

The reachability problems and shortest-path problems have been extensively
studied not only for general graphs but also for special classes of graphs;
directed planar graphs [9], Euclidean spanners [8, 17], and disk-intersection
graphs [3, 5]. In the following, we introduce several results for transmission
graphs of disks in the plane. Let $\Psi$ be the ratio between the largest and
the smallest radii associated with the points in $P$.

  * •

$t$-Spanners (Single-source reachability problem). One can solve the single-
source reachability problem for transmission graphs in $O(n\log^{4}n)$ time by
constructing a dynamic data structures for weighted nearest neighbor queries
[4, 14]. Kaplan et al. [13] presented two algorithms for the more general
problem that asks to compute a $t$-spanner of size $O(n)$ for any constant
$t>1$, one with $O(n\log^{4}n)$ time and one with $O(n\log n+n\log\Psi)$ time.
Recently, Ashur and Carmi [2] also considered this problem, and presented an
$O(n^{2}\log n)$-time algorithm for computing a $t$-spanner of which every
node has a constant in-degree, and the total weight is bounded by a function
of $n$ and $\Psi$. Also, spanners for transmission graphs in an arbitrary
metric space also have been considered [18, 19].

  * •

Discrete reachability oracles. Kaplan et al. [11] presented three reachability
oracles: one for $\Psi<\sqrt{3}$, two for an arbitrary $\Psi>1$. For an
arbitrary $\Psi$, their first reachability oracle has performance which
polynomially depends on $\Psi$, and the second one has performance which
polylogarmically depends on $\Psi$. More specifically, the first data
structure uses space $O(\Psi^{3}n^{1/2})$, and has query time
$O(\Psi^{5}n^{3/2})$. The second one uses space $\tilde{O}_{n,\Psi}(n^{5/3})$,
and has query time $\tilde{O}_{n,\Psi}(n^{2/3})$, where $\tilde{O}_{n,\Psi}$
hides polylogarithmic factors in $\Psi$ and $n$. This data structure is
randomized in the sense that it allows to answer all queries correctly with
high probability.

  * •

Continuous reachability oracles. Kaplan et al. [13] shows that a discrete
reachability oracle for the transmission graph $G$ of $P$ can be extended to a
continuous reachability oracle. More specifically, given a discrete
reachability oracle for $G$ with space $S(n)$ and query time $Q(n)$, one can
obtain in $O(n\log n\log\Psi)$ time a continuous reachability oracle for $G$
with space $S(n)+O(n\log\Psi)$ and query time $O(Q(n)+\log n\log\Psi)$.

###  1.2 Our Results.

As mentioned above, we improve the previously best-known results of the three
versions of the reachability problem for transmission graphs.

  * •

$t$-Spanners (Single-source reachability problem). We first present an
$O(n\log^{3}n)$-time algorithm for computing a $t$-spanner for a constant
$t>0$ in Section 2, which improves the running time of the algorithm by [13]
by a factor of $O(\log n)$. Our construction is based on the $\Theta$-graph
and grid-like range tree introduced by [16]. This algorithm is also used for
computing reachability oracles in Sections 3 and 5, and Section 4.

  * •

Discrete reachability oracles. We present two discrete reachability oracles
for the transmission graph of $P$. The first one described in Section 3 uses
space $O(n^{5/3})$ and has query time $O(n^{2/3})$, and can be computed in
$O(n^{5/3})$ time. This is the first reachability oracle for a transmission
graph whose performance is independent of $\Psi$.

The second one is described in Section 4. Its performance parameters depend
polylogarithmically on the radius ratio $\Psi$. More specifically, it uses
space $\tilde{O}_{\Psi}(n^{5/2})$, and has query time
$\tilde{O}_{\Psi}(n^{3/2})$. It can be constructed in
$\tilde{O}_{\Psi}(n^{5/2})$, where $\tilde{O}_{\Psi}(\cdot)$ hides
polylogarithmic factors in $\Psi$. To obtain this, we combine two reachability
oracles given by [11] whose performance parameters using a balanced separator
of smaller size introduced by [7].

  * •

Continuous reachability oracles. We also present a _continuous reachability
oracle_ with space $O(n^{5/3})$, query time $O(n^{2/3})$, and preprocessing
time $O(n^{5/3}\log^{2}n)$ in Section 5, which is the first continuous
reachability oracle whose performance is independent of $\Psi$. Instead of
using the approach in [13], we use auxiliary data structures whose performance
is independent of $\Psi$ together with the reachability oracle described in
Section 3.

##  2 Improved Algorithm for Computing a $t$-Spanner

Let $P$ be a set of $n$ points associated with radii, and $G=(P,E)$ be the
transmission graph of $P$. A subgraph $H$ of $G$ is called a _t-spanner_ of
$G$ if for every pair of vertices of $G$, the distance in $H$ between them is
at most $t$ times the distance in $G$ between them. A _sparse_ $t$-spanner is
useful for constructing a reachability oracle efficiently; a $t$-spanner
preserves the reachability information of $G$, and it allows us to investigate
a small number of edges. Therefore, we first consider the problem of
constructing a $t$-spanner of $G$ in this section, and we use it for
constructing a reachability oracle in Section 3.

In this section, we present an $O(n\log^{3}n)$-time algorithm for computing a
$t$-spanner of $G$ of size $O(n)$ for any constant $t>1$. This improves the
running time of the algorithm proposed by Kaplan et al. [11], which runs in
$O(n\log^{4}n)$ time.111 Kaplan et al. mentioned that this algorithm takes an
$O(n\log^{5}n)$ time. However, this can be improved automatically into
$O(n\log^{4}n)$ using a data structure of [4]. The spanner constructed by
Kaplan et al. is a variant of the Yao graph. They first show that a variant of
the Yao graph is a $t$-spanner for $G$, and then show how to construct it
efficiently.

###  2.1 Theta Graphs and $t$-Spanners of Transmission Graphs

Our spanner construction is based on the _$\Theta$ -graph_, which is a
geometric spanner similar to the Yao graph. Let $k>0$ be a constant, which
will be specified later, depending on $t$. Imagine that we subdivide the plane
into $k$ interior-disjoint cones with opening angle $2\pi/k$ which have the
origin as their apexes. Let $\mathcal{F}$ be the set of such cones. See Figure
1(a). For a cone $F\in\mathcal{F}$ and a point $p\in P$, let $F_{p}$ denote
the translated cone of $F$ so that the apex of $F_{p}$ lies on $p$. For each
point $p\in P$, we pick $k$ incoming edges for $p$, one for each cone of
$\mathcal{F}$, as follows.

For a point $q$ contained in $F_{p}$, let $q_{\ell}$ denote the the orthogonal
projection of $q$ on the angle-bisector of $F_{p}$. Also, we let $d_{F}(p,q)$
be the Euclidean distance between $p$ and $q_{\ell}$, and let
$\textsc{n}_{F}(p)$ denote the point $q$ in $F_{p}$ with ${(q,p)}\in E$ that
minimizes $d_{F}(p,q)$. See Figure 1(b). Note that $\textsc{n}_{F}(p)$ might
not exist. For each cone $F\in\mathcal{F}$ and each point $p\in P$, we choose
${(\textsc{n}_{F}(p),p)}$. See Figure 1(c). Let $H_{k}$ be the graph
consisting of the points in $P$ and the chosen edges. If it is clear from the
context, we simply use $H$ to denote $H_{k}$.

Figure 1: Theta graph construction for $k=8$. (a) The $k$ cones of
$\mathcal{F}$ subdivides the plane. (b) $\textsc{n}_{F}(p)=y$, and
$\textsc{n}_{S}(p)=y$. (c) The edge ${(y,p)}$ is picked.

To show that the $H_{k}$ forms a $t$-spanner, we need the following technical
lemma.

######  Lemma 1.

For a point $p$ in $P$ and a cone $F$ in $\mathcal{F}$, consider two points
$u$ and $v$ contained in $F_{p}$ such that ${(u,p)}\in E$ and ${(v,p)}\in E$.
Suppose the opening angle of $F$ is smaller than $\pi/3$, that is, $k>6$. If
$d_{F}(p,v)<d_{F}(p,u)$, then ${(u,v)}\in E$ and $|uv|<|up|$.

Proof. Consider the triangle bounded by the boundary of $F_{p}$ and a line
through $u$ orthogonal to the angle-bisector of $F_{p}$. Notice that this
triangle is an isosceles triangle containing $v$. Since the top angle of the
triangle is smaller than $\pi/3$, the apex $p$ is the farthest point from $u$
within the triangle. This implies $|uv|<|up|$. Since $r_{u}$ is at least
$|up|$, the edge ${(u,v)}$ is contained in $E$.

######  Lemma 2.

For an integer $k>8$, $H_{k}$ is a
$\tan(\frac{\pi}{4}+\frac{2\pi}{k})$-spanner of $G$.

Proof. We want to show that for every edge $e={(u,p)}$ in $G$, there is a path
in $H_{k}$ from $u$ to $p$ whose length is at most
$\tan(\frac{\pi}{4}+\frac{2\pi}{k})\cdot|up|$. Let
$t=\tan(\frac{\pi}{4}+\frac{2\pi}{k})$.

To show this, we use the induction on the length of the edges. For the base
case, assume that ${(u,p)}$ is the shortest edge of the transmission graph.
Let $F$ be the cone of $\mathcal{F}$ such that $F_{p}$ contains $u$. By
construction, the directed edge from $\textsc{n}_{F}(p)$ to $p$ is an edge of
$H$. Let $v=\textsc{n}_{F}(p)$. If $u=v$, then ${(u,p)}$ is an edge of $H$,
and thus we are done. Otherwise, ${(u,v)}$ is an edge of the transmission
graph $G$ by Lemma 1, and moreover, it is shorter than ${(u,p)}$, which
contradicts that ${(u,p)}$ is the shortest edge of $G$.

Now consider an edge ${(u,p)}$, and suppose that for every edge in the
transmission graph shorter than ${(u,p)}$, there is a path connecting them
whose length is at most $t$ times their Euclidean distance. Let $F$ be the
cone of $\mathcal{F}$ such that $F_{p}$ contains $u$. By construction, the
directed edge from $\textsc{n}_{F}(p)$ to $p$ is an edge of $H$. Let
$v=\textsc{n}_{F}(p)$. If $u=v$, then ${(u,p)}$ is an edge of $H$, and thus we
are done. Thus in the following, we assume that $u\neq v$. In this case,
${(u,v)}$ is an edge of the transmission graph $G$ by Lemma 1, and moreover,
it is shorter than ${(u,p)}$.

Therefore, there is a path $\pi$ from $v$ to $p$ whose length is at most
$t|vp|$ by the induction hypothesis. Since ${(u,v)}$ is an edge of $G$, the
concatenation of $\pi$ and ${(u,v)}$ is a path of $G$ whose length is at most
$|uv|+t|vp|$. Let $s$ be the projection point of $v$ to ${(u,p)}$. See Figure
2. We consider two cases with respect to the position of $s$.

Since
$t=\tan(\frac{\pi}{4}+\frac{2\pi}{k})=\frac{1+\tan(\frac{2\pi}{k})}{1-\tan(\frac{2\pi}{k})}$,
we have $\frac{t-1}{t+1}=\tan(\frac{2\pi}{k})>\tan(\frac{\pi}{k})$.

Figure 2: Two cases of the location of $s$

##### Case 1.

Suppose $s$ lies on ${(u,p)}$. See Figure 2(a). Since $u,v$ and $s$ are
contained in $F_{p}$, we have $\angle upv\leq 2\pi/k$. Then,

$\displaystyle|vp|+t|uv|$ $\displaystyle<|ps|+|sv|+t(|us|+|sv|)$
$\displaystyle=t(|us|+|ps|)+(t+1)|sv|+(1-t)|ps|.$

Note that $|sv|=|ps|\tan(\angle upv)$ and $\tan(\angle
upv)\leq\tan(2\pi/k)=\frac{t-1}{t+1}$. We obtain $(t+1)|sv|\leq(t-1)|ps|$.
Then,

$\displaystyle t(|us|+|ps|)+(t+1)|sv|+(1-t)|ps|$ $\displaystyle\leq
t(|us|+|ps|)$ $\displaystyle=t|up|$

##### Case 2.

Now suppose $s$ does not lie on $up$. See Figure 2(b) for illustration. Let
$x$ be an intersection point of the line through $pv$ and the line $l$ that
passes $u$ which is orthogonal to the angle bisecting line of the cone. Also,
let $y$ be a projection point of $p$ into $l$. Similarly, by Lemma 1, there is
a path $\pi$ from $u$ to $v$ such that the length of $\pi$ is less than
$t|uv|$ by the induction hypothesis. Also, we consider the concatenation of
$\pi$ and edge $vp$. Then, the length of this path is

$\displaystyle|vp|+t|uv|$ $\displaystyle\leq|px|+t|ux|$
$\displaystyle<|py|+(t+1)|yx|$ $\displaystyle<(1+(t+1)\tan(\pi/k))|py|\ \
(\because\tan(\angle yps)\leq\tan(\pi/k))$
$\displaystyle<(1+(t+1)\tan(\pi/k))|up|$ $\displaystyle\leq t|up|\ \
(\because\tan(\pi/k)<(t-1)/(t+1)).$

#####

Therefore, for any case, there is a path from $u$ to $p$ with its length at
most $t|up|$. This completes the proof.

Note that $t=\tan(\frac{\pi}{4}+\frac{2\pi}{k})>1$ converges to
$\tan(\frac{\pi}{4})=1$ as $k\rightarrow\infty$. Therefore, for any constant
$t>1$, we can find a constant $k$ such that $H_{k}$ is a $t$-spanner of the
transmission graph.

###  2.2 Efficient Algorithm for Computing the $t$-Spanner

In this section, we give an $O(n\log^{3}n)$-time algorithm to construct
$H_{k}$ for a constant $k>6$. To compute all edges of $H_{k}$, for each point
$p\in P$ and each cone $F\in\mathcal{F}$, consider the translated cone $F_{p}$
of $F$ so that the apex lies on $p$, and compute $\textsc{n}_{F}(p)$. We show
how to do this for a cone $F\in\mathcal{F}$ only. The others can be handled
analogously. Without loss of generality, we assume that the counterclockwise
angle from the positive $x$-axis to two rays of $F$ are $0$ and $2\pi/k$,
respectively. Let $\ell_{1}$ and $\ell_{2}$ be two lines orthogonal to the two
rays, respectively.

##### Approach of Kaplan et al.

The spanner constructed by Kaplan et al. [11] is a variation of the Yao graph.
For each cone $F\in\mathcal{F}$ and a point $p\in P$, they pick the closest
point in $F_{p}$ to $p$ among all points $q$ with $p\in D_{q}$. Since they
choose the closest point in a cone with respect to the Euclidean distance,
they need to fit grid cells into a cone. To resolve this, they use various
data structures including a compressed quadtree, a power diagram, a well-
separated pair decomposition, and a dynamic nearest neighbor search data
structure.

##### Our Approach.

Instead, our construction is based on the $\Theta$-graph. Recall that we pick
the closest point in a cone with respect to $d_{F}(\cdot,\cdot)$ instead of
the Euclidean distance. The order of the points of $F_{p}\cap P$ sorted with
respect to $d_{F}(p,\cdot)$ is indeed the order of them sorted with respect to
their projection points onto the angle-bisector of $F$.

In the following, we present an $O(n\log^{3}n)$-time algorithms for computing
all edges of $H_{k}$ constructed for $F$. To do this, we use grid-like range
trees proposed by Moidu. et al. [16] together with a power diagram. With a
slight abuse of notation, for a region $S$ contained in $F_{p}$, let
$\textsc{n}_{S}(p)$ be the point $q$ of $S\cap P$ with ${(q,p)}\in E$ that
minimizes $d_{F}(p,q)$. See Figure 1(b).

####  2.2.1 Data structures.

We construct the _two-level grid-like range tree_ introduced by Moidu et al.
[16] with respect to $\ell_{1}$ and $\ell_{2}$. It is a two-level balanced
binary search tree. The first-level tree $T_{1}$ is a balanced binary search
tree on the $\ell_{1}$-projections of the points of $P$. Each node $\alpha$ in
the first-level tree corresponds to a slab $I(\alpha)$ orthogonal to
$\ell_{1}$. It is also associated with the second-level tree $T_{\alpha}$
which is a binary search tree, not necessarily balanced, on the points of
$P\cap I(\alpha)$. Unlike the standard range tree [6], $T_{\alpha}$ is
obtained from a balanced binary search tree $T_{2}$ on the
$\ell_{2}$-projections of the points of $P$. More specifically, we remove the
subtrees rooted at all nodes of $T_{2}$ whose corresponding parallelograms
contain no point in $P\cap I(\alpha)$ in their union, and contract all nodes
which have only one child. Then $T_{\alpha}$ is not necessarily balanced but a
full binary tree of depth $O(\log n)$.

Given a point $p$ of $P$, there are $O(\log^{2}n)$ interior-disjoint
parallelograms whose union contains all points of $P\cap F_{p}$. We denote the
set of these parallelograms by $\mathcal{B}_{p}$. By construction, the cells
of $\mathcal{B}_{p}$ are aligned for any point $p\in P$ so that we can
consider them as a grid of size $O(\log n)\times O(\log n)$. See Figure 3.

######  Lemma 3 ([16]).

The two-level grid-like range tree on a set of $n$ points in the plane can be
computed in $O(n\log n)$ time. Moreover, its size is $O(n\log n)$.

Then for each node $v$ of the second-level trees, we construct a balanced
binary search tree of the $\ell$-projections of $P\cap B(v)$ as the third-
level tree, where $\ell$ denotes the angle bisector of $F$. For a node $\beta$
of the third-level trees, let $P(\beta)$ denote the set of the points stored
in the subtree rooted at $\beta$. we construct the power diagram of
$P(\beta)$. The _power diagram_ is a weighted version of the Voronoi diagram.
More specifically, the _power distance_ between a point $p$ and a disk $D_{q}$
is defined as $|pq|^{2}-r_{q}^{2}$. The power diagram partitions the plane
into $n$ regions such that all points in a same region have the same closest
disk in power distance. The power diagram of $n$ disks can be constructed in
$O(n\log n)$ time with $O(n)$ space. Also, we can locate the disk $D$ that
minimizes the power distance from a query point $p$ in $O(\log n)$ time. As a
consequence, we can determine in $O(\log n)$ time if the query point $p$ is in
the union of disks by checking if $p\in D$ [10, 14].

The construction time of the first, second, and third-level trees is
$O(n\log^{3}n)$ in total. Then we construct the power diagram for each node of
a third-level tree in a _bottom-up_ fashion. In particular, we start from
constructing the power diagrams of the leaf nodes. For each internal node, we
compute its power diagram by merging the power diagram of its two children.
Therefore, we can construct the power diagrams for all nodes of a third-level
tree in $O(m\log m)$ time, where $m$ denotes the number of points
corresponding to the root of the third-level tree. Since the sum of $m$’s over
all third-level trees is $O(n\log^{2}n)$, the whole data structure can be
constructed in $O(n\log^{3}n)$ time.

####  2.2.2 Query algorithm.

For each cell $B\in\mathcal{B}_{p}$, we compute $\textsc{n}_{B}(p)$ in
$O(\log^{2}n)$ as follows. We start from the root of the third-level tree
associated with $B$. We check if there is a point $q\in P(\beta)$ with
${(q,p)}\in E$ using the power diagram stored in the root node. If it does not
exist, $\textsc{n}_{B}(p)$ does not exist. Otherwise, we traverse the third-
level tree until we reach a leaf node. For each node $\beta$ we encounter
during the traversal, we consider the left child of $\beta$, say $\beta_{L}$.
We check if there is a point $q\in P(\beta_{L})$ with ${(q,p)}\in E$ using the
power diagram stored in $\beta_{L}$. If it exists, we move to $\beta_{L}$.
Otherwise, we move to the right child of $\beta$. We do this until we reach a
leaf node, which stores $\textsc{n}_{B}(p)$.

In the following, we show how to choose $O(\log n)$ cells of
$\mathcal{B}_{p}$, one of which contains $\textsc{n}_{B}(p)$. The cells of
$\mathcal{B}_{p}$ are aligned along $\ell_{1}$ and $\ell_{2}$. They can be
considered as a grid of $O(\log n)\times O(\log n)$ cells. We represent each
row (parallel to $\ell_{1}$) by integers $1,\ldots,O(\log n)$, and each column
(parallel to $\ell_{2})$ by integers $1,\ldots,O(\log n)$. We represent each
cell of $\mathcal{B}_{p}$ by a pair $B(i,j)$ of indices such that $i$ is the
row-index and $j$ is the column-index of the cell. For illustration, see
Figure 3(a). A cell $B=B(i,j)$ is said to be _useful_ if $\textsc{n}_{B}(p)$
exists. Also, a useful cell $B=B(i,j)$ is called an _extreme cell_ of
$\mathcal{B}_{p}$ if no cell $B(i^{\prime},j^{\prime})$ is useful for indices
$i^{\prime}$ and $j^{\prime}$ such that $i-j=i^{\prime}-j^{\prime}$ and
$i^{\prime}<i$.

######  Lemma 4.

The cell of $\mathcal{B}_{p}$ containing $\textsc{n}_{F}(p)$ is an extreme
cell. Moreover, the number of extreme cells of $\mathcal{B}_{p}$ is $O(\log
n)$.

Proof. Suppose $\textsc{n}_{B}(p)$ exists for $B=B(i,j)$. For each integer
$w>0$, $B(i+w,j+w)$ lies in the upper right part of $B(i,j)$. This means that
$d_{F}(p,q)$ is at least $d_{F}(p,q^{\prime})$ for any two points $q\in
B(i+w,j+w)$ and $q^{\prime}\in B(i,j)$. Thus, the cell containing
$\textsc{n}_{F}(p)$ is an extreme cell.

The number of extreme cells is equal to the number of distinct $i-j$ values
among the cells $B(i,j)\in\mathcal{B}_{p}$. This number is $O(\log n)$ since
each index of rows and columns is a positive integer at most $O(\log n)$.

Figure 3: (a) Index of the grid-like range tree (b) Useful cells are colored
with gray or red, and extreme cells are colored red.

To compute $\textsc{n}_{F}(p)$, we first compute $\mathcal{B}_{p}$ in
$O(\log^{2}n)$ time. For each cell $B\in\mathcal{B}_{p}$, we check if it is
useful using the power diagram of $P\cap B$, which is stored in the root node
of the third-level tree in $O(\log^{3}n)$ time in total. Then we choose
$O(\log n)$ extreme cells among the useful cells of $\mathcal{B}_{p}$. For
each cell $B$ of them, we compute $\textsc{n}_{B}(p)$ in $O(\log^{2}n)$ time,
and thus the total query time is $O(\log^{3}n)$.

######  Theorem 5.

Given a point set $P$ and a constant $t>1$, we can construct a $t$-spanner of
the transmission graph of $P$ within $O(n\log^{3}n)$ time.

###  2.3 Computing a BFS Tree Using a $t$-Spanner

In this section, we construct a BFS tree for the transmission graph $G$. For a
root $s$, a _BFS tree_ is a shortest-path tree of $G$ rooted at $s$ where the
length of a path is measured by the number of edges in the path.

Kaplan et al. proposed an algorithm of constructing a BFS tree via their
$t$-spanner that is a variant of the Yao Graph. They utilize the technique
proposed by Cabello et al. [3] for their algorithm and correctness. Our
algorithm is exactly the same as the algorithm by Kaplan et al. However, since
our $t$-spanner is based on the $\Theta$-graph instead of the Yao Graph, we
have to prove the correctness.

For a given root $s$ of a BFS tree, let $W_{i}$ be the set of points in $P$
with depth $i$. The correctness of the algorithm follows from the following
lemma.

######  Lemma 6.

Let $H$ be a $t$-spanner as in Theorem 5, and let $v\in W_{i+1}$. Then, there
is a path $\pi=up_{k}\ldots p_{1}v$ in $H$ with $u\in W_{i}$ and $p_{j}\in
W_{i+1}$ for all indices $j\in[1,k]$.

Proof. For a point $v\in W_{i+1}$, let $s(v)$ denote the smallest Euclidean
distance between $v$ and a point $u\in W_{i}$ such that ${(u,v)}\in E$. We
prove the lemma using induction on $s(\cdot)$ for the points in $W_{i+1}$.

For the base case, let $v\in W_{i+1}$ have the smallest value of $s(v)$. Let
$u\in W_{i}$ be the point with $s(v)=|uv|$. If $u=\textsc{n}_{F}(v)$ for a
cone $F$ of $\mathcal{F}$, we are done. Otherwise, we consider the cone
$F\in\mathcal{F}$ such that $F_{v}$ contains $u$, and we consider
$w=\textsc{n}_{F}(v)$. By Lemma 1, ${(u,w)}$ and ${(w,v)}$ are edges of the
transmission graph. Also, $|uw|$ is less than $|uv|=s(v)$. Let $k$ be the
index with $w\in W_{k}$. We have $k\leq i+1$ since $u\in W_{i}$ and
${(u,w)}\in E$. Moreover, $k\neq i+1$. (Otherwise, $s(w)<s(v)$, which makes
contradiction.) Also, $k\geq i$ since ${(w,v)}\in E$ and $v\in W_{i+1}$.
Therefore, $\pi=wv$ is desired path because $w\in W_{i}$.

Now, we consider a node $v\in W_{i+1}$, and suppose that all $v^{\prime}\in
W_{i+1}$ with $s(v^{\prime})<s(v)$ satisfy the condition. Similarly, if
$u=\textsc{n}_{F}(v)$, we are done. Otherwise, we consider
$w=\textsc{n}_{F}(v)$ where $F_{v}$ contains $u$. The same properties hold by
Lemma 1. In particular, $w\in W_{k}$ with $k=i$ or $k=(i+1)$. If $k=i$, we are
done. Otherwise, $s(v)=|uv|>|uw|\geq s(w)$. Now, there is a path
$\pi=up_{k}...p_{1}w$ with $u\in W_{i}$ and $p_{j}\in W_{i+1}$ for all $j$ due
to the induction hypothesis on $w$. Then, the path
$\pi^{\prime}=up_{k}...p_{1}wv$ satisfies the condition. This completes the
induction.

Cabello et al. proposed a BFS tree algorithm for unit-disk graphs by
considering the edges of the Delaunay triangulation of the point set. Later,
Kaplan et al. proposed a $t$-spanner based on a variation of the Yao graph.
Their t-spanner provides similar properties for transmission graphs as the
Delaunay triangulation does for unit-disk graphs. Our $t$-spanner also
satisfies this property by Lemma 6. Indeed, Lemma 6 is the same as [3, Lemma
1] except that $H$ is our spanner in Lemma 6 and it is the Delaunay
triangulation in [3, Lemma 1]. Then, we are able to reuse the algorithm of
Cabello et al. We remark that this algorithm takes $O(n\log n)$ time.

######  Theorem 7.

Let $P$ be a set of $n$ points, each associated with a radius. Given a
$t$-spanner $H$ of the transmission graph $G$ of $P$ as in Theorem 5, we can
construct a BFS tree of $G$ within $O(n\log n)$ time.

##  3 Reachability Oracle for Unbounded Radius Ratio

In this section, we present a data structure of size $O(n^{5/3})$ so that
given any two points $p$ and $q$ in $P$, we can check if $p$ is reachable from
$q$ in $O(n^{2/3})$ time. Moreover, this data structure can be constructed in
$O(n^{5/3})$ time. Note that this result is independent to the radius ratio
$\Psi$.

We say a set of disks is $k$-_thick_ if for any point $p$ in the plane, there
are at most $k$ disks that contains $p$. Similarly, we say a transmission
graph is $k$-_thick_ if its underlying disk set is $k$-thick.

######  Lemma 8 ([15, Theorem 5.1]).

For any set $\mathcal{D}$ of disks that is $k$-thick, there is a circle $S$
intersecting $O(\sqrt{kn})$ disks of $\mathcal{D}$ such that the number of
disks of $\mathcal{D}$ with
$|S_{\textnormal{in}}|,|S_{\textnormal{out}}|\leq\frac{2n}{3}$, where
$S_{\textnormal{in}}$ and $S_{\textnormal{out}}$ denote the set of disks of
$\mathcal{D}$ contained in the interior of $S$ and the exterior of $S$,
respectively. In this case, We call $S$ a _separating circle_. Moreover, we
can compute $S$, $S_{\textnormal{in}}$ and $S_{\textnormal{out}}$ in linear
time.

Consider a separating circle $S$ of the disk set induced by $P$. By Lemma 8,
$P$ is partitioned into three sets $S_{\textnormal{in}},S_{\textnormal{out}}$,
and $S_{\textnormal{cross}}=\\{p\in P\mid D_{p}\cap S\neq\emptyset\\}$ such
that every path in $G$ connecting a point of $S_{\textnormal{in}}$ and a point
of $S_{\textnormal{out}}$ visits a point in $S_{\textnormal{cross}}$. We call
$S_{\textnormal{cross}}$ a _separator_ of $G$ (or $P$). Using separators, we
build a _separation tree_ by repeatedly applying the algorithm in Lemma 8. As
we will see in Section 3.2, the separation tree enables us to construct a
reachability oracle efficiently. However, the transmission graph of a set of
$n$ points is $n$-thick in the worst case, and in this case, Lemma 8 does not
give a non-trivial bound.

To resolve this, we partition $P$ into $O(n^{2/3})$ _chains_ , each consisting
of $O(n^{1/3})$ points of $P$, and the _remaining set_ $R$ of points of $P$
not belonging to any of the chains. Then we show that $R$ is
$O(n^{1/3})$-thick, and thus Lemma 8 gives an efficient reachability oracle
for the subgraph of $G$ induced by $R$. Additionally, we construct an
auxiliary data structure for each chain.

Figure 4:  (a) A set $P$ of points associated with radii. (b) The disks in the
same chain are colored with the same color, and the points in $R$ are colored
black.

###  3.1 Chain

We call a sequence $\langle p_{1},\ldots,p_{k}\rangle$ of points of $P$ sorted
in the ascending order of their associated radii a _chain_ if
${(p_{j},p_{i})}\in E$ for all indices $i$ and $j$ with $1\leq i<j$. In other
words, $|p_{i}p_{j}|\leq r_{p_{j}}$. In this section, we construct
$O(n^{1/3})$-length chains as many as possible so that the remaining set $R$
is $k$-thick for a small $k$.

To compute chains, we need a dynamic data structure for a set $\mathcal{D}$ of
disks, dynamically changing by insertions and deletions, such that for a query
point, we can check if there is a disk of $\mathcal{D}$ that contains the
query point. This can be obtained using dynamic 3-D halfspace lower envelope
data structure, which is given by [4], together with the standard lifting
transformation. In particular, this data structure can be built in $O(n\log
n)$ time and its insertion time, deletion time and query time are
$O(\log^{2}n)$, $O(\log^{4}n)$ and $O(\log^{2}n)$, respectively. For the
convenience, we denote this data structure by $\mathsf{DNN}(\mathcal{D})$.

######  Lemma 9.

Let $\mathcal{D}$ be a set of disks, and $p$ be a point in the plane. Given
$\mathsf{DNN}(\mathcal{D})$, we can check if there are $n^{1/3}$ disks of
$\mathcal{D}$ containing $p$ in $O(n^{1/3}\log^{4}n)$ time. Moreover, if they
exist, we can return them, and delete them from $\mathcal{D}$ and
$\mathsf{DNN}(\mathcal{D})$ within the same time bound.

Proof. We find a disk containing $p$ in $\mathcal{D}$ using
$\mathsf{DNN}(\mathcal{D})$, and remove the returned disk from $\mathcal{D}$
and $\mathsf{DNN}(\mathcal{D})$. Note that $\mathsf{DNN}(\mathcal{D})$ returns
a disk if and only if there is a disk in $\mathcal{D}$ that contains the query
point. We repeat this $n^{1/3}$ times. If $n^{1/3}$ distinct disks are
returned, then we are done. Otherwise, there are less than $n^{1/3}$ disks
that contain $p$. In this case, we are required to insert all removed points
to $\mathcal{D}$ and $\mathsf{DNN}(\mathcal{D})$. This procedure applies
$O(n^{1/3})$ queries, insertions and deletions, so it takes
$O(n^{1/3}\log^{4}n)$ time in total.

Let $\mathcal{D}$ be the set of disks induced by $P$, and we construct
$\mathsf{DNN}(\mathcal{D})$. We choose the smallest disk $D_{p}$ of
$\mathcal{D}$ and remove $D_{p}$ from $\mathcal{D}$. Then we update
$\mathsf{DNN}(\mathcal{D})$ accordingly. We check if there are $n^{1/3}$ disks
of $\mathcal{D}$ containing the center $p$ of $D_{p}$ by applying the
algorithm in Lemma 9. If it returns $n^{1/3}$ disks, let $L_{p}$ be the set
consisting of $p$ and the centers of those disks. Since $\mathcal{D}$ is
updated, we can apply this procedure again. We do this until $\mathcal{D}$ is
empty. As a result of this repetition, we obtain sets $L_{p}$’s of points of
$P$. Note that the disks induced by $L_{p}$ contain $p$, and the number of
$L_{p}$’s is $O(n^{2/3})$.

Next, for each set $L_{p}$, we consider six interior-disjoint cones with
opening angle $\pi/3$ with apex $p$. For each cone $F$, we sort the points of
$L_{p}\cap F$ in the ascending order of their associated radii. Then we claim
that the sorted list is a chain, and thus we obtain six chains for each set
$L_{p}$. Therefore, we have $O(n^{2/3})$ chains in total.

######  Lemma 10.

The sequence of the points of $L_{p}\cap F$ sorted in the ascending order of
their associated radii is a chain.

Proof. Consider two points $x$ and $y$ in the given sequence such that $x$
lies before $y$ in the sequence. Note that $r_{x}\leq r_{y}$ by construction.
We show that ${(y,x)}\in E$. Let $\triangle_{y}$ be the regular triangle
surrounded by the two rays of $F$ and a line passing through $y$. Then, $p$,
one corner of $\triangle_{y}$, is one of the farthest points from $y$ within
$\triangle_{y}$. Thus, if $x$ is contained in $\triangle_{y}$, we have
$r_{y}\geq|yp|$ and $r_{y}\geq|yx|$, and thus ${(y,x)}\in E$. Otherwise,
$\triangle_{y}\subset\triangle_{x}$, and thus $\triangle_{x}$ contains $y$. In
this case, since $p$ is one of the farthest points from $x$ in
$\triangle_{x}$, $|yx|\leq|xp|\leq r_{x}\leq r_{y}$, and thus ${(y,x)}\in E$.

Therefore, we have a set $\mathcal{C}$ of $O(n^{2/3})$ chains of length
$O(n^{1/3})$. We call the set of points of $P$ not contained in any of the
chains of $\mathcal{C}$ the _remaining set_. Also, we use $\mathcal{R}$ to
denote the subgraph of $G$ induced by $R$, and call it the _remaining graph_.

######  Lemma 11.

The graph $\mathcal{R}$ is $6n^{1/3}$-thick.

Proof. We first claim that the remaining set $R$ does not have a
$n^{1/3}$-length chain. Assume to the contrary that there is a
$n^{1/3}$-length chain $C$, and let $p$ be the first point in $C$. At some
moment in the course of the algorithm, $D_{p}$ becomes the smallest disk of
$\mathcal{D}$. At this moment, all disks associated with the points in $C$ are
contained in $\mathcal{D}$. That is, at least $n^{1/3}$ disks of $\mathcal{D}$
contain $p$, and thus $p$ must be contained in a chain of $\mathcal{C}$, which
contradicts that $p$ is a point of $R$.

Then we show that $R$ is $6n^{1/3}$-thick. For any point $x$ in the plane, we
consider six interior-disjoint cones with opening angle $\pi/3$ with apex $x$.
For a cone $F$, consider the list $L$ of the points $p$ of $R\cap F$ with
$r_{p}\geq|px|$ sorted in the ascending order of their associated radii. The
proof of Lemma 10 implies that $L$ is a chain. By the claim mentioned above,
the size of $L$ is less than $n^{1/3}$. Now consider the union of the lists
for all of the six cones, which has size less than $6n^{1/3}$. Notice that it
is the set of all points $p\in P$ with $r_{p}\geq|px|$, and thus the lemma
holds.

By Lemma 9, we can compute all $L_{p}$’s in $O(n^{4/3}\log^{4}n)$ time, and
for each $L_{p}$, we can compute six chains in $O(n^{1/3}\log n)$ time. Since
the number of $L_{p}$’s is $O(n^{2/3})$, the total time for computing all
chains of $\mathcal{C}$ is $O(n^{4/3}\log^{4}n)$ time.

###  3.2 Separation tree of $\mathcal{R}$

In this section, we build a reachability oracle for $\mathcal{R}$, which is
similar to the reachability oracle proposed by Kaplan et al. [11, Section
4.2]. In this case, since $\mathcal{R}$ is $O(n^{1/3})$-thick, we can derive a
better result. Then Lemma 8 shows that there is a separator of size
$O(n^{2/3})$. Recall that $R$ is the vertex set of $\mathcal{R}$.

##### Data structure.

We construct the separation tree $T$ of $R$ recursively as follows. We compute
a separator $S_{\textnormal{cross}}$ of $\mathcal{R}$ and two subsets
$S_{\textnormal{in}}$ and $S_{\textnormal{out}}$ separated by
$S_{\textnormal{cross}}$. We recursively construct the separation trees of
$S_{\textnormal{in}}$ and $S_{\textnormal{out}}$. Then we make a new node $v$,
and connect $v$ with the roots of the separation trees of
$S_{\textnormal{in}}$ and $S_{\textnormal{out}}$. We let $G_{v}$ denote the
subgraph of $G$ induced by $R$. See Figure 5.

Figure 5: The remaining set and its separation tree

For each node $v$, we store the reachability information as follows: For every
point $p\in G_{v}$, we store two lists of points of $S_{\textnormal{cross}}$
which is reachable to $p$ and which is reachable from $p$ within $G_{v}$. In
particular, we construct a $2$-spanner of $G_{v}$. Then, for each point $s\in
S_{\textnormal{cross}}$, we apply the BFS algorithm in Section 2 from $s$.
Also, we reverse the spanner and again apply the BFS algorithm from $s$.

##### Query Algorithm.

Given two query points $p,q\in R$, we want to check if $q$ is reachable from
$p$ in $\mathcal{R}$. To do this, we observe the following. Let $v$ and $u$ be
the two nodes of the separation tree $T$ such that the separators of $G_{v}$
and $G_{u}$ contain $p$ and $q$, respectively. They are uniquely defined
because each point of $R$ is contained in exactly one separator stored in $T$.
Let $L$ be the path of $T$ from the lowest common ancestor of $v$ and $u$ to
the root. Consider a path $\pi$ from $p$ to $q$ in $\mathcal{R}$, if it
exists. By construction, there is a node $w$ in $L$ such that the separator of
$G_{w}$ intersects $\pi$. Among them, consider the node closest to the root
node. Then $G_{w}$ contains $\pi$. Therefore, it suffices to check if $q$ is
reachable from $p$ in $G_{x}$ for every node $x$ in $L$.

To use this observation, we first compute $v,u$ and $L$ in $O(\log n)$ time.
Then for each node $w$ of $L$, we check if there is a point $x$ in separator
such that $p$ is reachable to $x$ and $q$ is reachable from $x$ in $O(m)$
time, where $m$ denotes the size of the separator of $G_{w}$. We return
$\mathsf{YES}$ if and only if there is such a point $x$. Since the size of the
separators stored in each node is geometrically increasing along $L$, the
total size is dominated by the size of the separator of $R$, which is
$O(n^{2/3})$. Therefore, our query algorithm takes $O(n^{2/3})$ time.

######  Lemma 12.

We can construct a separation tree $T$ of $\mathcal{R}$ with associated
reachability information in $O(n^{5/3})$ time and $O(n^{5/3})$ space. Then, we
can query whether there is path from $p$ to $q$ in $\mathcal{R}$ within
$O(n^{2/3})$ time.

Proof. Since the analysis of the query time is presented in the above text, we
focus on the size of the data structure and its preprocessing time only. For
each node $v$ of the separation tree, we spend $O(m)$ time to compute a
separator and two separated subsets, $O(m\log^{3}m)$ time to compute a
2-spanner, and $O(m^{2/3})\cdot O(m)$ = $O(m^{5/3})$ time for the BFS
algorithm, where $m$ denotes the complexity of $G_{v}$.

Let $P(m)$ be the time for constructing the separation tree for a point set of
size $m$. Then we have $P(m)\leq P(m_{1})+P(m_{2})+O(m^{5/3})$, where $m_{1}$
and $m_{2}$ denote the size of $S_{\textnormal{in}}$ and
$S_{\textnormal{out}}$, respectively. Notice that $m_{1}+m_{2}\leq m$ and
$m_{1},m_{2}<2m/3$, and thus $P(n)=O(n^{5/3})$. Similarly, we can show that
the space complexity is $O(n^{5/3})$.

###  3.3 Chain Indices

In this section, we construct a reachability oracle for each chain
$C\in\mathcal{C}$: Given any two points $p$ and $q$ in $P$, we can check if
there is a path from $p$ to $q$ intersects $C$. For each chain $C=\langle
p_{1},...,p_{t}\rangle$, we can construct the oracle in $O(n)$ time once we
have a 2-spanner of $G$. To do this, we need the following lemma. See Figure
6.

######  Lemma 13.

For two points $p$ and $q$ in $P$, let $i$ be the largest index such that $p$
is reachable to $p_{i}$, and $j$ be the smallest index such that $p_{j}$ is
reachable to $q$. Then, there is a $p$-$q$ path that intersects $C$ if and
only if $j\leq i$.

Proof. If there is $p$-$q$ path that intersects $C$, there exists $p_{k}\in C$
such that $p$ is reachable to $p_{k}$ and $p_{k}$ is reachable to $q$. Then,
$j\leq k\leq i$. Conversely, if $j\leq i$, there exist a $p$-$p_{i}$ path, a
$p_{i}$-$p_{j}$ path, and a $p_{j}$-$q$ path by the choice of $i$ and $j$.
Then, the concatenation of those three paths is a $p$-$q$ path that intersects
$C$.

Figure 6: (a) There is a $p$-$q$ path via $C$ if $j(q)\leq i(p)$. (b) There is
no $p$-$q$ path that intersects $C$ if $j(q)>i(p)$

For every point $q\in P$, we store the largest index $i(q)$ such that $q$ is
reachable to $p_{i(q)}$, and store the smallest index $j(q)$ such that
$p_{j(q)}$ is reachable to $q$.

######  Lemma 14.

We can compute the indices $i(\cdot)$ and $j(\cdot)$ for every $q\in P$ and
every $C\in\mathcal{C}$ in $O(n^{5/3})$ time. Also, the total number of
indices we store is $O(n^{5/3})$.

Proof. In the following, we show how to compute $j(q)$ for every point $q\in
P$. The other index $i(q)$ can be computed similarly. Let $I_{j}$ be the set
of points $q\in P$ such that $j(q)=j$. That is, a point $q$ is contained in
$I_{j}$ if and only if $p_{i}$ is the first point of $C$ which is reachable to
$q$.

We compute $I_{1},\ldots,I_{t}$ one by one in order. For an index $\ell$,
assume that we maintain a graph $H_{\ell}$, which is the subgraph of the
2-spanner of $G$ induced by $\cup_{j=\ell}^{t}I_{j}$. We can compute
$I_{\ell}$ by applying the BFS algorithm on $H_{\ell}$ starting from
$p_{\ell}$. The set of all points we encountered is exactly $I_{\ell}$. To
maintain the invariant, we remove all points in $I_{\ell}$ and their adjacent
edges from $H_{\ell}$, and denote it by $H_{\ell+1}$. For each index $\ell$,
the BFS algorithm runs in $O(|I_{\ell}|)$ time. Since $I_{\ell}$’s are
pairwise disjoint, the BFS algorithm runs in $O(n)$ time in total. Since we
have $O(n^{2/3})$ chains, the total time for computing all chain indices is
$O(n^{5/3})$.

###  3.4 Reachability Oracles

Given two points $p,q\in P$, we can check if $p$ is reachable from $q$ as
follows. Suppose there is a $p$-$q$ path $\pi$. If there is a chain $C$ that
intersects $\pi$ at a point of $C$, say $p_{k}$. Then $j(q)\leq k\leq i(p)$
for the indices $j(q)$ and $i(p)$ stored in $C$ by Lemma 13. In this case, we
can find such a chain $C$ in $O(n^{2/3})$ time by computing indices $j(q)$ and
$i(p)$ for all chains of $\mathcal{C}$. Otherwise, no chain of $\mathcal{C}$
intersects $\pi$. Then $\pi$ is contained in $\mathcal{R}$, and thus we can
use the reachability oracle for $\mathcal{R}$ described in Section 3.2. This
takes $O(n^{2/3})$ by Lemma 12.

######  Theorem 15.

Given a set $P$ of points associated with radii, we can compute a reachability
oracle for the transmission graph of $P$ in $O(n^{5/3})$ time. The
reachability oracle has size $O(n^{5/3})$ and supports the query time
$O(n^{2/3})$.

##  4 Reachability Oracle for Small Radius Ratio

We improve the reachability of oracle described in Section 3 if $\Psi$ is
polynomial in $n$. In particular, we construct a reachability oracle with size
$O(n^{3/2}\log^{1/2}\Psi)$, query time $O(n^{1/2}\log^{1/2}\Psi)$, and
preprocessing time $O(n^{3/2}\log^{1/2}\Psi)$ time.

###  4.1 Hierarchical Grid

For an index $i\in\\{0,1,...\\}$, consider the partition of the plane into
axis-parallel squares (cells) with diameter $2^{i}$ such that the origin lies
in the corner of a cell. We call this the _grid_ at level $i$, and denote it
by $\mathcal{Q}_{i}$. We consider the $L$ grids
$\mathcal{Q}_{0},...,\mathcal{Q}_{L}$ where $L$ = $\lceil\log{\Psi}\rceil$.
For each cell $\sigma\in\mathcal{Q}_{i}$, let $P_{\sigma}$ be the set of
points $p$ in $P\cap\sigma$ such that $r_{p}\in[2^{i},2^{i+1})$. Note that
every point is contained in $P_{\sigma}$ for exactly one cell $\sigma$ for all
grids $\mathcal{Q}_{1},\ldots,\mathcal{Q}_{L}$.

We construct a new graph $H=(V^{\prime},E^{\prime})$ where $V^{\prime}$ is the
set of cells $\sigma$ with $P_{\sigma}\neq\emptyset$, and $E^{\prime}$ is the
set of pairs $(\sigma_{1},\sigma_{2})$ such that there are two points $p\in
P_{\sigma_{1}}$ and $q\in P_{\sigma_{2}}$ with ${(p,q)}\in E$. Note that the
points in $P_{\sigma}$ form a clique, and thus it suffices to construct a
reachability oracle for $H$.

######  Lemma 16.

We can construct $H=(V^{\prime},E^{\prime})$ from the transmission graph $G$
within $O(n\log n\log\Psi)$ time. Moreover, the number of edges of $H$ is
$O(|V^{\prime}|\log\Psi)$.

Proof. For every cell $\sigma$ with $P_{\sigma}\neq\emptyset$, we construct
the power diagram of $P_{\sigma}$. This takes $O(n\log n)$ time for all cells
in total. We define a grid cluster as a block of $9\times 9$ contiguous grid
cells. For every point $p\in P_{\sigma}$ and for every grid level $i=0,...,L$,
let $C(p,i)$ denote the grid cluster of grid level $i$ whose center grid cell
contains $p$.

For each index $i\in[1,L]$ and each cell $\sigma$, we want to find all edges
${(\sigma,\sigma^{\prime})}$ such that $\sigma^{\prime}$ is a cell of
$\mathcal{Q}_{i}$. For a cell $\sigma^{\prime}$ of $\mathcal{Q}_{i}$,
${(\sigma,\sigma^{\prime})}\in E^{\prime}$ if and only if ${(p,q)}\in E$ for
two points $p\in\sigma$ and $q\in\sigma^{\prime}$. Then, the Euclidean
distance between $p$ and the center of $\sigma^{\prime}$ is at most
$2^{i}+2^{i+1}=3\cdot 2^{i}$. Therefore, $\sigma^{\prime}\in C(p,i)$. Thus, we
can compute all edges ${(\sigma,\sigma^{\prime})}$ such that $\sigma^{\prime}$
is a cell of $\mathcal{Q}_{i}$ by considering the cells in $C(p,i)$ for every
$p\in P_{\sigma}$. In particular, for every cell $\sigma^{\prime}$ in
$C(p,i)$, we check if there is a point $q\in P_{\sigma^{\prime}}$ with
${(q,p)}\in E$ using the power diagram within $O(|P_{\sigma}|\log n)$ time.
Since $C(p,i)$ has $O(1)$ cells, we can do this for all cells in $C(p,i)$ in
$O(|P_{\sigma}|\log n)$ time. In total, we can compute every edge in
$E^{\prime}$ in $O(n\log n\log\Psi)$ time since $L=\log\Psi$ and the total
size of $P_{\sigma}$ for all levels $i$ and all cells in $\mathcal{Q}_{i}$ is
$n$.

We want to compute the number of edges in $E^{\prime}$. To do this, we first
consider $(\sigma,\sigma^{\prime})\in E^{\prime}$ such that
$\sigma\in\mathcal{Q}_{i}$ and $\sigma\in\mathcal{Q}_{j}$ with $j<i$. Then,
there are two points $p\in P_{\sigma}$ and $q\in P_{\sigma^{\prime}}$ such
that ${(p,q)}\in E$. Since $r_{q}>r_{p}$ by construction, ${(q,p)}\in E$, and
thus $(\sigma^{\prime},\sigma)\in E$. Therefore, it suffices to compute the
number of edges in $E^{\prime}$ from $\sigma^{\prime}\in\mathcal{Q}_{j}$ to
$\sigma\in\mathcal{Q}_{i}$ where $i\leq j$.

For a cell $\sigma\in\mathcal{Q}_{i}$, we show that the number of incoming
edges from cells in $\mathcal{Q}_{j}$ to $\sigma$ is $O(1)$ for every $j\geq
i$. Let $\sigma_{j}$ be a cell in $\mathcal{Q}_{j}$ such that
$\sigma\subseteq\sigma_{j}$. Then, for every $p\in P_{\sigma}$, $C(p,i)$ is
equal to the grid cluster with center cell $\sigma_{j}$. Therefore, all
incoming edges for $\sigma$ from the cells in $\mathcal{Q}_{j}$ are contained
in the grid cluster with center cell $\sigma_{j}$. Then, the total number of
incoming edges from the cells in $\cup_{k=i}^{L}\mathcal{Q}_{k}$ to $\sigma$
is $O(\log\Psi)$. This shows that the number of edges of $H$ is
$O(|V^{\prime}|\log\Psi)$.

###  4.2 Separation tree revisited

Now we want construct a reachability oracle for $H$. We construct the
separation tree described in Section 3.2. We slightly make the additional step
because now the graph $H$ consists of cells instead of points with associated
radii. For each cell $\sigma\in V^{\prime}\cap\mathcal{Q}_{i}$ with its center
$c(\sigma)$, we associate radius $3\cdot 2^{i}$ with $c(\sigma)$ and let
$D(\sigma)$ be the associated disk. We denote the set of all centers of cells
of $V^{\prime}$ by $X$.

We first show that $X$ is $O(\log\Psi)$-thick. That is, any point $p$ in the
plane is contained in $O(\log\Psi)$ associated disks of the points of $X$. For
a grid level $i$ and a cell $\sigma\in\mathcal{Q}_{i}$, consider the
associated disk of $c(\sigma)$ containing $p$. Then, $\sigma$ is contained in
the block of $9\times 9$ contiguous grid cells of level $i$ whose center grid
cell contains $p$. Therefore, $p$ is contained in $O(1)$ associated disks of
$c(\sigma)$ for cells of grid level $i$. Since the number of grids is
$L=O(\log\Psi)$, $X$ is $O(\log\Psi)$-thick.

##### Data structure.

We construct the separation tree $T$ for $X$ as follows. We compute a
separator $S_{\textnormal{cross}}$ of $X$ and two subsets
$S_{\textnormal{in}}$ and $S_{\textnormal{out}}$ separated by
$S_{\textnormal{cross}}$. We recursively construct the separation trees of
$S_{\textnormal{in}}$ and $S_{\textnormal{out}}$. Then we make a new node $v$,
and connect $v$ with the roots of the separation trees of
$S_{\textnormal{in}}$ and $S_{\textnormal{out}}$. Let $H_{v}$ be the subgraph
of $H$ induced by $X$.

For each node $v$ of $T$, we store the reachability information as follows.
For every point $c(\sigma)\in S_{\textnormal{cross}}$, we store two lists of
cells of $H_{v}$ which are reachable to $\sigma$ and which are reachable from
$\sigma$ within $H_{v}$. In particular, for each cell $\sigma$ where
$c(\sigma)\in S_{\textnormal{cross}}$, we apply a breadth-first search from
$\sigma$ in $H_{v}$. Also, we reverse $H_{v}$ and again apply a breadth-first
search from $\sigma$.

##### Construction time.

For each node $v$ of $T$, we spend $O(m)$ time to compute a separator and two
separated subsets, where $m$ denotes the vertices of $H_{v}$. The size of the
separator is $O(m^{1/2}\log^{1/2}\Psi)$ because $X$ is $O(\log\Psi)$-thick.
Moreover, the number of edges of $H_{v}$ is $O(m\log\Psi)$ by Lemma 16. Thus
we can apply a breath-first search in $O(m^{3/2}\log^{3/2}\Psi)$ time.

Let $P(m)$ be the time for constructing the separation tree for a point set of
size $m$. Then we have $P(m)\leq P(m_{1})+P(m_{2})+O(m^{3/2}\log^{3/2}\Psi)$,
where $m_{1}$ and $m_{2}$ denote the size of $S_{\textnormal{in}}$ and
$S_{\textnormal{out}}$, respectively. Notice that $m_{1}+m_{2}\leq m$ and
$m_{1},m_{2}<2m/3$, and thus $P(n)=O(m^{3/2}\log^{3/2}\Psi)$. Similarly, we
can show that the space complexity is $O(m^{3/2}\log^{1/2}\Psi)$. But in this
case, the space used by each node of $T$ is $O(n^{3/2}\log^{1/2}\Psi)$ instead
of $O(n^{3/2}\log^{3/2}\Psi)$.

##### Query Algorithm.

Given two query cells $\sigma_{1},\sigma_{2}\in H$, we want to check if
$\sigma_{2}$ is reachable from $\sigma_{1}$ in $H$. To do this, we observe the
following. Let $v$ and $u$ be the two nodes of the separation tree $T$ such
that the separators of $G_{v}$ and $G_{u}$ contain $c(\sigma_{1})$ and
$c(\sigma_{2})$, respectively. Let $L$ be the path of $T$ from the lowest
common ancestor of $v$ and $u$ to the root.

Note that $D(\tau)$ intersects $D(\tau^{\prime})$ for any two cells $\tau$ and
$\tau^{\prime}$ of $V^{\prime}$ with ${(\tau,\tau^{\prime})}\in E^{\prime}$.
Consider a node $w\in T$ and the separator $S_{\textnormal{cross}}$ of
$G_{w}$. Let $S_{\textnormal{in}}$ and $S_{\textnormal{out}}$ be the two sets
separated by $S_{\textnormal{cross}}$. Also, for any two cells $\sigma$ and
$\sigma^{\prime}$ of $V^{\prime}$ with $c(\sigma)\in S_{\textnormal{in}}$ and
$c(\sigma^{\prime})\in S_{\textnormal{out}}$, a
$D(\sigma)$-$D(\sigma^{\prime})$ path in the (undirected) disk intersection
graph of $X$ intersects the associated disk of a point of
$S_{\textnormal{cross}}$. Therefore, a $\sigma$-$\sigma^{\prime}$ path in $H$
intersects a cell $\sigma^{\prime\prime}$ where $c(\sigma^{\prime\prime})\in
S_{\textnormal{cross}}$.

This implies that for any path $\pi$ from $\sigma_{1}$ to $\sigma_{2}$ in $H$,
there is a node $x$ in $L$ such that $\pi$ intersects a cell $\sigma$ such
that $c(\sigma)\in S$, where $S\subseteq X$ denotes the separator of $G_{x}$.
Among them, consider the node closest to the root node. Then $G_{w}$ contains
$\pi$. Therefore, it suffices to check if $\sigma_{2}$ is reachable from
$\sigma_{1}$ in $G_{w}$ for all nodes $w\in L$.

To use this observation, we first compute $v,u$ and $L$ in $O(\log n)$ time
since $T$ has $O(\log n)$ levels. Then for each node $u$ of $L$, we check if
the separator of $G_{u}$ contains $c(\sigma)$ such that $\sigma_{1}$ is
reachable to $\sigma$ and $\sigma_{2}$ is reachable from $\sigma$ in $O(k)$
time, where $k$ denotes the size of the separator of $G_{u}$. We return
$\mathsf{YES}$ if there is such a node $u$. Otherwise, we return
$\mathsf{NO}$. Since the size of the separators stored in each node is
geometrically increasing along $L$, the total size is dominated by the size of
the separator of $X$, which is $O(n^{1/2}\log^{1/2}\Psi)$. Therefore, our
query algorithm takes $O(n^{1/2}\log^{1/2}\Psi)$ time.

######  Theorem 17.

Given a set $P$ of points associated with radii and $P$ has radius ratio
$\Psi$, we can compute a reachability oracle for the transmission graph of $P$
in $O(n^{3/2}\log^{3/2}\Psi)$ time. The reachability oracle has size
$O(n^{3/2}\log^{1/2}\Psi)$ and supports the query time
$O(n^{1/2}\log^{1/2}\Psi)$.

##  5 Continuous Reachability Oracle

In this section, we present a continuous reachability oracle which its
complexity is independent of the radius ratio $\Psi$. In particular, our data
structure has size $O(n^{5/3})$ so that for any two point $s\in P$ and
$t\in\mathbb{R}^{2}$, we can check if $s$ is reachable to $t$ in
$O(n^{2/3}\log^{2}n)$ time. Also, this data structure can be constructed in
$O(n^{5/3})$ time. If $t$ is reachable from $s$, there is a point $p\in P$
reachable from $s$ with $t\in D_{p}$. In this case, we define a _$s$ -$t$
path_ in $G$ as the concatenation of a $s$-$p$ path in $G$ and the segment
connecting $p$ and $t$.

Consider two query points $s\in P$ and $t\in\mathbb{R}^{2}$. If there is a
$s$-$t$ path $\pi$, we denote the vertex incident to $t$ in $\pi$ by $p(\pi)$.
We construct auxiliary data structures for $R$ and $\mathcal{C}$ to handle the
following two cases. We first consider the case that there is a $s$-$t$ path
$\pi$ with $p(\pi)\in R$. In this case, we choose a set $R_{0}$ of $O(1)$
points in $R$ so that there is a $s$-$t$ path $\pi^{\prime}$ with
$p(\pi^{\prime})\in R_{0}$ if and only if there is a $s$-$t$ path $\pi$ with
$p(\pi)\in R$. If it is not the case, for any $s$-$t$ path $\pi$, $p(\pi)$ is
contained in a chain of $\mathcal{C}$. We can handle this by investigating
every chain of $\mathcal{C}$, and finding the first point in the chain whose
associated disk contains $t$. In addition to this, we construct the discrete
reachability oracle for $G$ described in Section 3.

###  5.1 The remaining set $R$, revisited

We construct the data structure so that we can check if there is a $s$-$t$
path $\pi$ with $p(\pi)\in R$. To do this, wee construct the $O(n)$-sized data
structure proposed by Afshani and Chan [1] such that for $P$ and a query point
$t$, we can find all points in $P$ whose associated disks contain
$t\in\mathbb{R}^{2}$ in $O(\log n+k)$ time, where $k$ is the number of disks
that contain $t$. Moreover, it can be constructed in $O(n\log n)$ time. Since
$R$ is $O(n^{1/3})$-thick, this query time is bounded by $O(n^{1/3})$.

Given two points $p\in P$ and $t\in\mathbb{R}^{2}$, we compute a set $R_{t}$
of $O(n^{1/3})$ points of $P$ whose associated disks contain $t$ within
$O(n^{1/3})$ time. Then we choose a subset $R_{0}$ of $R_{t}$ of size $O(1)$
such that there is a $s$-$t$ path $\pi^{\prime}$ with $p(\pi^{\prime})\in
R_{0}$ if and only if there is a $s$-$t$ path $\pi$ with $p(\pi)\in R$.

######  Lemma 18.

Assume that we are given a point $t\in\mathbb{R}^{2}$ and a set $R_{t}$ of
points of $R$ whose associated disks contain $t$. We can compute a
$O(1)$-sized set $R_{0}\subset R_{t}$ such that $R_{0}\cap D_{p}\neq\emptyset$
for every point $p\in R_{t}$ in $O(|R_{t}|)$ time.

Proof. We consider six interior-disjoint cones with opening angle $\pi/3$ with
apex $t$. For a cone $F$, we consider the list $L$ of the points $p\in
R_{t}\cap F$. We pick the point $q\in L$ that minimizes the distance value
$d_{F}(t,\cdot)$. (For the definition of $d_{F}(t,\cdot)$, see the beginning
of Section 2.1.) We claim that for every point $x\in L$, the associated disk
of $x$ contains $q$. Let $\triangle$ be the regular triangle surrounded by the
two rays of $F$ and a line passing through $x$. Then, $t$ is one of the
farthest points from $x$ within $\triangle$. Also, $q$ is contained in
$\triangle$ by the definition of $q$. Therefore, $|qx|\leq|tx|\leq r_{x}$, and
thus $D_{x}$ contains $q$. Then, the set of points $q$ from all cone $F$
satisfy the condition of $R_{0}$. This procedure takes $O(n^{1/3})$ time.

Then we can answer the continuous reachability query using the discrete
reachability oracle for all points $q\in R_{0}$ in $O(n^{2/3})$ time by
Theorem 15.

###  5.2 The set $\mathcal{C}$ of chains, revisited.

We construct a data structure for each chain $C\in\mathcal{C}$ so that we can
compute the first point in $C$ which contains $t$. To do this, we construct a
balanced binary search tree of the indices in $[1,t]$ for $C=\langle
p_{1},\ldots,p_{t}\rangle$. For each node $u$ of the binary search tree, we
construct the power diagram of the points stored in the subtree rooted at $u$.
Note that this data structure is a variation of the third-level tree proposed
in Section 2.2. We sort the points along their indices here, while we sort the
points along $\ell$-projections in Section 2.2. Therefore, as we showed in
Section 2.2, the construction takes $O(m\log m)$ time, and we can compute the
first point in $C$ which contains $t$ within $O(\log^{2}m)$ time for each
chain $C$, where $m=|C|$. In this way, we can construct the auxiliary data
structures for all chains of $\mathcal{C}$ in $O(n\log n)$ time.

Given two points $s\in P$ and $t\in\mathbb{R}^{2}$, we can check if $s$ is
reachable to $t$ as follows. Suppose there is a $s$-$t$ path $\pi$. If
$p(\pi)$ is contained in a chain $C\in\mathcal{C}$, let $k$ be the index of
$p(\pi)$ in $C=\langle p_{1},\ldots,p_{t}\rangle$, that is, $p_{k}=p(\pi)$. We
let $j(t)$ denote the index of the first point in $C$ which contains $t$, and
let $i(s)$ denote the index of the last point in $C$ which is reachable from
$s$. Recall that $i(s)$ is stored in the discrete reachability oracle, and
$j(t)$ can be computed using the auxiliary data structure for $C$ as mentioned
above. Then there is a $s$-$t$ path $\pi$ with $p(\pi)\in C$ if and only if
$j(t)\leq k\leq i(s)$. We do this for all chains in $\mathcal{C}$. Since we
can compute the first point that contains $t$ for every chain of $\mathcal{C}$
in $O(n^{2/3}\log^{2}n)$ time, the total query time is $O(n^{2/3}\log^{2}n)$
time. Therefore, we have the following theorem.

######  Theorem 19.

Given a set $P$ of points associated with radii, we can compute a continuous
reachability oracle for the transmission graph of $P$ in $O(n^{5/3})$ time.
The reachability oracle has size $O(n^{5/3})$ and supports the query time
$O(n^{2/3}\log^{2}n)$.

## References

  * [1] P. Afshani and T. Chan.  Optimal halfspace range reporting in three dimensions.  In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pages 180–186, 2009.
  * [2] S. Ashur and P. Carmi.  t-spanners for transmission graphs using the path-greedy algorithm.  In 36th European Workshop on Computational Geometry (EuroCG 2020), Book of Abstracts, pages 60:1–60:6, 2020.
  * [3] S. Cabello and M. Jejčič.  Shortest paths in intersection graphs of unit disks.  Computational Geometry, 48(4):360–367, 2015.
  * [4] T. M. Chan.  Dynamic geometric data structures via shallow cuttings.  In Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), pages 24:1–24:13, 2019.
  * [5] T. M. Chan and D. Skrepetos.  Approximate shortest paths and distance oracles in weighted unit-disk graphs.  Journal of Computational Geometry, 10(2):3–20, 2019.
  * [6] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars.  Computational Geometry: Algorithms and Applications.  Springer-Verlag TELOS, 2008.
  * [7] J. Fox and J. Pach.  Separator theorems and turán-type results for planar intersection graphs.  Advances in Mathematics, 219(3):1070–1080, 2008.
  * [8] J. Gudmundsson, C. Levcopoulos, G. Narasimhan, and M. Smid.  Approximate distance oracles for geometric spanners.  ACM Transactions on Algorithms, 4(1):1–34, 2008.
  * [9] J. Holm, E. Rotenberg, and M. Thorup.  Planar reachability in linear space and constant time.  In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), pages 370–389, 2015.
  * [10] H. Imai, M. Iri, and K. Murota.  Voronoi diagram in the Laguerre geometry and its applications.  SIAM Journal on Computing, 14(1):93–105, 1985.
  * [11] H. Kaplan, W. Mulzer, L. Roditty, and P. Seiferth.  Spanners and reachability oracles for directed transmission graphs.  In Proceedings of the 31st International Symposium on Computational Geometry (SoCG 2015), pages 156–170, 2015.
  * [12] H. Kaplan, W. Mulzer, L. Roditty, and P. Seiferth.  Routing in unit disk graphs.  Algorithmica, 80(3):830–848, 2018.
  * [13] H. Kaplan, W. Mulzer, L. Roditty, and P. Seiferth.  Spanners for directed transmission graphs.  SIAM Journal on Computing, 47(4):1585–1609, 2018.
  * [14] H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, and M. Sharir.  Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2495–2504, 2017.
  * [15] G. Miller, S.-H. Teng, and S. Varasis.  A unified geometric approach to graph separators.  In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), pages 538–547, 1991.
  * [16] N. Moidu, J. Agarwal, and K. Kothapalli.  Planar convex hull range query and related problems.  In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), 2013.
  * [17] E. Oh.  Shortest-path queries in geometric networks.  In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 52:1–52:15, 2020.
  * [18] D. Peleg and L. Roditty.  Localized spanner construction for ad hoc networks with variable transmission range.  ACM Transactions on Sensor Networks, 7(3):1–14, 2010.
  * [19] D. Peleg and L. Roditty.  Relaxed spanners for directed disk graphs.  Algorithmica, 65(1):146–158, 2013.
  * [20] P. Von Rickenbach, R. Wattenhofer, and A. Zollinger.  Algorithmic models of interference in wireless ad hoc and sensor networks.  IEEE/ACM Transactions on Networking, 17(1):172–185, 2009.
  * [21] H. Wang and J. Xue.  Near-optimal algorithms for shortest paths in weighted unit-disk graphs.  Discrete & Computational Geometry, 64(4):1141–1166, 2020.