ML p(r)ior | Spanners for Directed Transmission Graphs

Spanners for Directed Transmission Graphs

2016-01-28
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.
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-09-28

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

Highlights - Most important sentences from the article

2018-07-16

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

Highlights - Most important sentences from the article

2018-11-16

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

Highlights - Most important sentences from the article

2019-03-19

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

Highlights - Most important sentences from the article

2019-03-12
1903.05255 | cs.CG

We revisit a classical graph-theoretic problem, the \textit{single-source shortest-path} (SSSP) prob… show more
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2016-11-02

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

Highlights - Most important sentences from the article

2018-11-30

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-10-25

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

Highlights - Most important sentences from the article

2019-01-11

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

Highlights - Most important sentences from the article

2018-11-05

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

Highlights - Most important sentences from the article

2018-12-24

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

Highlights - Most important sentences from the article

2017-08-02

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

Highlights - Most important sentences from the article