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

Reachability Oracles for Directed Transmission Graphs

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

Highlights - Most important sentences from the article

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

Related Articles

2018-03-19

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

Highlights - Most important sentences from the article

2018-11-29

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

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
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-02-25

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

Highlights - Most important sentences from the article

2017-10-20

Analyzing massive complex networks yields promising insights about our everyday lives. Building scal… 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

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

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
PDF

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
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-04-12

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