### Reachability Oracles for Directed Transmission Graphs

**2016-01-28**

1601.07797 | cs.CG

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.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-03-19**

1803.06977 | cs.DS

For fixed $h \geq 2$, we consider the task of adding to a graph $G$ a set of
weighted shortcut edges… show more

**2018-11-29**

1811.12527 | cs.DS

The diameter, radius and eccentricities are natural graph parameters. While
these problems have been… show more

**2018-08-07**

1808.02568 | cs.DS

We present a data structure that, given a graph $G$ of $n$ vertices and $m$
edges, and a suitable pa… show more

**2018-09-28**

1809.11147 | cs.CG

For any constant $d$ and parameter $\varepsilon > 0$, we show the existence
of (roughly) $1/\varepsi… show more

**2018-07-16**

1807.05968 | cs.DS

We consider exact distance oracles for directed weighted planar graphs in the
presence of failing ve… show more

**2018-11-16**

1811.06898 | cs.CG

We show how to construct $(1+\varepsilon)$-spanner over a set $P$ of $n$
points in $\mathbb{R}^d$ th… show more

**2019-02-25**

1902.09228 | cs.DS

We consider the problem of designing succinct data structures for interval
graphs with $n$ vertices … show more

**2017-10-20**

1710.07565 | cs.DC

Analyzing massive complex networks yields promising insights about our
everyday lives. Building scal… show more

**2018-12-10**

1812.03960 | cs.CG

We study unit ball graphs (and, more generally, so-called noisy uniform ball
graphs) in $d$-dimensio… show more

**2016-11-02**

1611.00721 | cs.DS

The girth of a graph, i.e. the length of its shortest cycle, is a fundamental
graph parameter. Unfor… show more

**2019-01-31**

1901.11285 | cs.CC

Reachability is the problem of deciding whether there is a path from one
vertex to the other in the … show more

**2018-09-20**

1809.07481 | cs.CG

Let $P$ be a simple polygon of $n$ vertices. We consider two-point $L_1$
shortest path queries in $P… show more

**2018-10-25**

1810.10982 | cs.DS

The discrete Fr\'echet distance is a popular measure for comparing polygonal
curves. An important va… show more

**2019-01-11**

1901.03615 | cs.DS

Computing the Strongly-Connected Components (SCCs) in a graph $G=(V,E)$ is
known to take only $O(m +… show more

**2018-04-12**

1804.05013 | cs.DM

We provide new connectivity results for {\em vertex-random graphs} or {\em
random annulus graphs} wh… show more

**2018-11-05**

1811.01551 | cs.DS

We present new tradeoffs between space and query-time for exact distance
oracles in directed weighte… show more