ML p(r)ior | Reachability Oracles for Directed Transmission Graphs

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.

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-11-29
1811.12527 | cs.DS

Highlights - Most important sentences from the article

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

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-02-25 1902.09228 | cs.DS We consider the problem of designing succinct data structures for interval graphs with$n$vertices … show more Highlights - Most important sentences from the article 2017-10-20 1710.07565 | cs.DC Analyzing massive complex networks yields promising insights about our everyday lives. Building scal… 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 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 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 Highlights - Most important sentences from the article 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

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-04-12
1804.05013 | cs.DM

We provide new connectivity results for {\em vertex-random graphs} or {\em random annulus graphs} wh… 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