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

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.

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

Highlights - Most important sentences from the article

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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 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 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 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article