# Reachability Oracles for Directed Transmission Graphs

Research paper by **Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth**

Indexed on: **28 Jan '16**Published on: **28 Jan '16**Published in: **Computer Science - Computational Geometry**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Let $P \subset \mathbb{R}^d$ be a set of $n$ points in the $d$ dimensions
such that each point $p \in P$ has an associated radius $r_p > 0$. The
transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such
that there is an edge from $p$ to $q$ if and only if $d(p, q) \leq r_p$, for
any $p, q \in P$.
A reachability oracle is a data structure that decides for any two vertices
$p, q \in G$ whether $G$ has a path from $p$ to $q$. The quality of the oracle
is measured by the space requirement $S(n)$, the query time $Q(n)$, and the
preprocessing time. For transmission graphs of one-dimensional point sets, we
can construct in $O(n \log n)$ time an oracle with $Q(n) = O(1)$ and $S(n) =
O(n)$. For planar point sets, the ratio $\Psi$ between the largest and the
smallest associated radius turns out to be an important parameter. We present
three data structures whose quality depends on $\Psi$: the first works only for
$\Psi < \sqrt{3}$ and achieves $Q(n) = O(1)$ with $S(n) = O(n)$ and
preprocessing time $O(n\log n)$; the second data structure gives $Q(n) =
O(\Psi^3 \sqrt{n})$ and $S(n) = O(\Psi^5 n^{3/2})$; the third data structure is
randomized with $Q(n) = O(n^{2/3}\log^{1/3} \Psi \log^{2/3} n)$ and $S(n) =
O(n^{5/3}\log^{1/3} \Psi \log^{2/3} n)$ and answers queries correctly with high
probability.