Let $P$ be a set of $n$ points in the plane, each with an associated radius $r_p > 0$. The transmission graph $G$ for $P$ has vertex set $P$ and an edge from $p$ to $q$ if and only if $q$ lies in the ball with radius $r_p$ around $p$. A reachability oracle for $G$ is a data structure that answers reachability queries: given two vertices, is there a directed path between them? The quality of the oracle is measured by the used space $S(n)$, the query time $Q(n)$, and the preproccesing time.

We present three different data structures whose quality depends on $\Psi$, the ratio of the largest and smallest radius of two points in $P$: (i) if $\Psi < \sqrt{3}$, we achieve $Q(n) = O(1)$ with $S(n) = O(n \log n)$; (ii) if $\Psi$ is constant, we get $Q(n) = O(\Psi^3 \sqrt{n})$ and $S(n) = O(\Psi^3 n^{3/2})$; and (iii) if $\Psi$ is polynomially bounded in $n$, we use probabilistic methods to obtain an oracle with $S(n) = O(n^{5/3} \log n)$ and $Q(n) = O(n^{2/3} \log n)$ that answers queries correctly with high probability. The construction time is $O(n^{5/3} \log^2 n)$.

To achieve a fast preproccesing time, we show how to compute a $t$-spanner $H$ for $G$ in time $O(n (\log n + \log \Psi))$. More precisely, $H$ is a sparse subgraph of $G$ such that for any two vertices $p$,$q$ connected by a path of length $l$ in $G$, there is a $p-q$-path of length at most $tl$ in $H$.

Joint work with Haim Kaplan, Wolfgang Mulzer, and Liam Roditty.