2022/10/11 by de Berg, Mark
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2210.05788
Let P be a set of n points in the plane, where each point p∈ P has a transmission radius r(p)>0. The transmission graph defined by P and the given radii, denoted by Gtr(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(n5/3) storage and, given two query points s,t∈ P, can decide in O(n2/3) time if there is a path from s to t in Gtr(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√(n)) and the query time to O(√(n)). Our oracle can be extended to approximate distance queries: we can construct, for a given parameter ε>0, an oracle that uses O((n/ε)√(n)log n) storage and that can report in O((√(n)/ε)log n) time a value dhop^*(s,t) satisfying dhop(s,t) ≤ dhop^*(s,t) < (1+ε)⋅ dhop(s,t) + 1, where dhop(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 ℝd can be constructed in O(nlog n) time.