### Spanners for Directed Transmission Graphs

**2016-01-28**

1601.07798 | cs.CG

Let $P \subset \mathbb{R}^2$ be a planar $n$-point set 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 for any $p, q \in P$,
there is an edge from $p$ to $q$ if and only if $d(p, q) \leq r_p$.
Let $t > 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H \subseteq
G$ with vertex set $P$ so that for any two vertices $p,q \in P$, we have
$d_H(p, q) \leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path
distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show
how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (\log n + \log
\Psi))$ time, where $\Psi$ is the ratio of the largest and smallest radius of a
point in $P$. Using more advanced data structures, we obtain a construction
that runs in $O(n \log^5 n)$ time, independent of $\Psi$.
We give two applications for our spanners. First, we show how to use our
spanner to find a BFS tree in $G$ from any given start vertex in $O(n \log n)$
time (in addition to the time it takes to build the spanner). Second, we show
how to use our spanner to extend a reachability oracle to answer geometric
reachability queries. In a geometric reachability query we ask whether a vertex
$p$ in $G$ can "reach" a target $q$ which is an arbitrary point in the plane
(rather than restricted to be another vertex $q$ of $G$ in a standard
reachability query). Our spanner allows the reachability oracle to answer
geometric reachability queries with an additive overhead of $O(\log n\log
\Psi)$ to the query time and $O(n \log \Psi)$ to the space.

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

# Related Articles

**2018-09-27**

1809.10531 | cs.CG

In the range closest pair problem, we want to construct a data structure
storing a set $S$ of $n$ po… 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-03-19**

1903.08263 | cs.DS

Let $R$ and $B$ be two point sets in $\mathbb{R}^d$, with $|R|+ |B| = n$ and
where $d$ is a constant… show more

**2019-03-12**

1903.05255 | cs.CG

We revisit a classical graph-theoretic problem, the \textit{single-source
shortest-path} (SSSP) prob… 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

**2017-09-22**

1709.07797 | cs.CG

We consider a simple graph-based metric on points in Euclidean space known as
the edge-squared metri… 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

**2018-11-30**

1811.12547 | cs.DS

We introduce the inverse Voronoi diagram problem in graphs: given a graph $G$
with positive edge-len… show more

**2019-02-26**

1902.10051 | cs.CG

The unit disk graph (UDG) is a widely employed model for the study of
wireless networks. In this mod… 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-11-05**

1811.01551 | cs.DS

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

**2018-12-24**

1812.09913 | cs.CG

For any constants $d\ge 1$, $\epsilon >0$, $t>1$, and any $n$-point set
$P\subset\mathbb{R}^d$, we s… show more

**2017-08-02**

1708.00814 | cs.CG

Let $P$ be a planar set of $n$ sites in general position. For
$k\in\{1,\dots,n-1\}$, the Voronoi dia… show more