Reachability Oracles for Directed Transmission Graphs

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul SeiferthAlgorithmica 2016 · DOI · OpenReview

Abstract

Let $P \subset \mathbb{R}^d$ be a set of $n$ points in $d$ dimensions where each point $p \in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for $P$ is a directed graph where an edge exists from $p$ to $q$ if and only if $|pq| \leq r_p$. This paper explores reachability oracles—data structures that efficiently determine if a path exists between any two vertices $p$ and $q$. For one-dimensional sets, we achieve $O(1)$ query time with $O(n)$ space. For two-dimensional sets, the radius ratio $\Psi$ (largest to smallest radius) is critical. We present three primary data structures: an $O(1)$ query oracle for $\Psi < \sqrt{3}$, a deterministic oracle for general $\Psi$, and a randomized oracle achieving sub-linear query times for large $\Psi$.

Introduction

In the study of wireless sensor networks, the "reachability" problem asks a simple but vital question: can a message sent from one sensor eventually reach another? Modeling these networks as directed transmission graphs allows us to account for varying broadcast powers. However, answering reachability queries in general directed graphs typically requires a trade-off between massive $O(n^2)$ storage or slow $O(n)$ search times.

This paper provides a breakthrough by exploiting the geometric properties of transmission graphs to create "reachability oracles" that offer both low space requirements and fast query responses. By focusing on the dimensionality of the point set and the ratio of broadcast radii, the authors provide a suite of solutions tailored to different network constraints.

The Transmission Graph Model

A transmission graph $G = (P, E)$ is defined by a set of points $P$ in Euclidean space. Unlike standard unit disk graphs where all radii are equal, transmission graphs allow each point $p$ to have its own radius $r_p$. This asymmetry leads to directed edges: if $p$ is within range of $q$ but $q$ is not within range of $p$, communication is one-way.

A transmission graph illustrating the complex directed connectivity between two sets of points in different regions.

The complexity of reachability in these graphs depends heavily on the spatial distribution and the variance in broadcast ranges. The paper introduces the parameter $\Psi$, representing the ratio between the maximum and minimum radii in the set, as a primary factor in determining the efficiency of the resulting oracle.

Methods for Reachability

One-Dimensional Networks

In a one-dimensional setting, the reachability problem simplifies significantly. The authors observe that the set of points reachable from any vertex $p$ forms a single continuous interval on the line. This geometric property allows for the construction of an oracle using $O(n)$ space that can answer any reachability query in $O(1)$ time after $O(n \log n)$ preprocessing.

The $\sqrt{3}$ Threshold and Planarization

For two-dimensional networks, the authors identify a critical threshold: $\Psi < \sqrt{3}$. When broadcast radii are relatively uniform (within this $\sqrt{3}$ factor), the graph's geometric constraints prevent complex overlapping that usually hinders efficiency.

Specifically, the authors demonstrate that such graphs can be "planarized." By identifying crossing edges and resolving them through the addition of a linear number of dummy vertices, the transmission graph is transformed into a planar graph that preserves all original reachability relationships.

The planarization process: resolving crossing edges by introducing a dummy vertex $x$, which preserves reachability while creating a planar structure.

Once planarized, the graph can leverage existing, highly optimized reachability oracles designed for planar topologies, resulting in $O(1)$ query times and linear space.

Handling Large Radius Ratios

When the radius ratio $\Psi$ is large, the planarization technique no longer applies. To address this, the paper introduces two alternative approaches:

  1. Geometric Separators: This method uses a separator theorem for disks to recursively partition the plane. By building a "separator tree," the oracle can efficiently track how paths cross between different regions of the network.
  2. Randomized Sampling: This hybrid strategy targets two types of paths. "Long" paths, which consist of many hops, are likely to be intercepted by a small random sample of vertices. "Short" paths, which stay within a local neighborhood, are handled using a hierarchical grid or quadtree structure. This randomized approach achieves a query time of approximately $O(n^{2/3})$ with $O(n^{5/3})$ space.

Key Results and Complexity

The following table summarizes the performance of the proposed oracles:

Graph Type Space $S(n)$ Query Time $Q(n)$ Preprocessing
1D Transmission $O(n)$ $O(1)$ $O(n \log n)$
2D ($\Psi < \sqrt{3}$) $O(n)$ $O(1)$ $O(n \log n)$
2D (General, Det.) $O(\Psi^3 n^{3/2})$ $O(\Psi^3 \sqrt{n})$ -
2D (General, Rand.) $O(n^{5/3} \text{polylog})$ $O(n^{2/3} \text{polylog})$ -

Conclusion

This research demonstrates that geometric properties can significantly simplify reachability problems that are otherwise difficult in general directed graphs. While the $\sqrt{3}$ bound provides a powerful tool for near-uniform networks, future work remains to determine if similar efficiencies can be achieved for larger radius ratios or if this threshold represents a fundamental limit of the model.

Summary updated

Abstract

Let $$P \subset \mathbb {R}^d$$ P⊂Rd be a set of n points in d dimensions such that each point $$p \in P$$ p∈P has an associated radius$$r_p > 0$$ rp>0. The transmission graphG for P is the directed graph with vertex set P such that there is an edge from p to q if and only if $$|pq| \le r_p$$ |pq|≤rp, for any $$p, q \in P$$ p,q∈P. A reachability oracle is a data structure that decides for any two vertices $$p, q \in G$$ p,q∈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)$$ O(nlogn) time an oracle with $$Q(n) = O(1)$$ Q(n)=O(1) and $$S(n) = O(n)$$ 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}$$ Ψ<3 and achieves $$Q(n) = O(1)$$ Q(n)=O(1) with $$S(n) = O(n)$$ S(n)=O(n) and preprocessing time $$O(n\log n)$$ O(nlogn); the second data structure gives $$Q(n) = O(\Psi ^3 \sqrt{n})$$ Q(n)=O(Ψ3n) and $$S(n) = O(\Psi ^3 n^{3/2})$$ S(n)=O(Ψ3n3/2); the third data structure is randomized with $$Q(n) = O(n^{2/3}\log ^{1/3} \Psi \log ^{2/3} n)$$ Q(n)=O(n2/3log1/3Ψlog2/3n) and $$S(n) = O(n^{5/3}\log ^{1/3} \Psi \log ^{2/3} n)$$ S(n)=O(n5/3log1/3Ψlog2/3n) and answers queries correctly with high probability.
BibTeX
@inproceedings{kaplan2016reachability,
  author = {Haim Kaplan and Wolfgang Mulzer and Liam Roditty and Paul Seiferth},
  title = {{Reachability Oracles for Directed Transmission Graphs}},
  booktitle = {Algorithmica},
  year = {2016},
  doi = {10.1007/s00453-019-00641-1},
}
Figure