Abstract
Let P be a set of n points in the plane, where each point p in P has a transmission radius r(p) > 0. The transmission graph defined by P and the given radii, denoted by G_{tr}(P), is the directed graph whose nodes are the points in P and that contains the arcs (p,q) such that |pq|≤ r(p).
An and Oh [Algorithmica 2022] presented a reachability oracle for transmission graphs. Their oracle uses O(n^5/3) storage and, given two query points s,t in P, can decide in O(n^2/3) time if there is a path from s to t in G_{tr}(P). We show that the clique-based separators introduced by De Berg et al. [SICOMP 2020] can be used to improve the storage of the oracle to O(n\sqrt{n}) and the query time to O(\sqrt{n}). Our oracle can be extended to approximate distance queries: we can construct, for a given parameter eps > 0, an oracle that uses O((n/\eps)\sqrt{n}\log n) storage and that can report in O((\sqrt{n}/\eps)\log n) time a value d*_{hop}(s,t) satisfying d_{hop}(s,t) \leq d*_{hop}(s,t) < (1+eps) d_{hop}(s,t) + 1, where d_{hop}(s,t) is the hop-distance from s to t. We also show how to extend the oracle to so-called continuous queries, where the target point t can be any point in the plane.
To obtain an efficient preprocessing algorithm, we show that a clique-based separator of a set F of convex fat objects in Rd can be constructed in O(n log n) time.
An and Oh [Algorithmica 2022] presented a reachability oracle for transmission graphs. Their oracle uses O(n^5/3) storage and, given two query points s,t in P, can decide in O(n^2/3) time if there is a path from s to t in G_{tr}(P). We show that the clique-based separators introduced by De Berg et al. [SICOMP 2020] can be used to improve the storage of the oracle to O(n\sqrt{n}) and the query time to O(\sqrt{n}). Our oracle can be extended to approximate distance queries: we can construct, for a given parameter eps > 0, an oracle that uses O((n/\eps)\sqrt{n}\log n) storage and that can report in O((\sqrt{n}/\eps)\log n) time a value d*_{hop}(s,t) satisfying d_{hop}(s,t) \leq d*_{hop}(s,t) < (1+eps) d_{hop}(s,t) + 1, where d_{hop}(s,t) is the hop-distance from s to t. We also show how to extend the oracle to so-called continuous queries, where the target point t can be any point in the plane.
To obtain an efficient preprocessing algorithm, we show that a clique-based separator of a set F of convex fat objects in Rd can be constructed in O(n log n) time.
| Original language | English |
|---|---|
| Pages (from-to) | 4:1 - 4:15 |
| Number of pages | 15 |
| Journal | Computing in Geometry and Topology |
| Volume | 2 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 11 May 2023 |