ALBERT

Description: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈span〉 〈span〉\(P \subset \mathbb {R}^d\)〈/span〉 〈/span〉 be a set of 〈em〉n〈/em〉 points in 〈em〉d〈/em〉 dimensions such that each point 〈span〉 〈span〉\(p \in P\)〈/span〉 〈/span〉 has an 〈em〉associated radius〈/em〉〈span〉 〈span〉\(r_p 〉 0\)〈/span〉 〈/span〉. The 〈em〉transmission graph〈/em〉〈em〉G〈/em〉 for 〈em〉P〈/em〉 is the directed graph with vertex set 〈em〉P〈/em〉 such that there is an edge from 〈em〉p〈/em〉 to 〈em〉q〈/em〉 if and only if 〈span〉 〈span〉\(|pq| \le r_p\)〈/span〉 〈/span〉, for any 〈span〉 〈span〉\(p, q \in P\)〈/span〉 〈/span〉. A 〈em〉reachability oracle〈/em〉 is a data structure that decides for any two vertices 〈span〉 〈span〉\(p, q \in G\)〈/span〉 〈/span〉 whether 〈em〉G〈/em〉 has a path from 〈em〉p〈/em〉 to 〈em〉q〈/em〉. The quality of the oracle is measured by the space requirement 〈em〉S〈/em〉(〈em〉n〈/em〉), the query time 〈em〉Q〈/em〉(〈em〉n〈/em〉), and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in 〈span〉 〈span〉\(O(n \log n)\)〈/span〉 〈/span〉 time an oracle with 〈span〉 〈span〉\(Q(n) = O(1)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(n)\)〈/span〉 〈/span〉. For planar point sets, the ratio 〈span〉 〈span〉\(\Psi \)〈/span〉 〈/span〉 between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on 〈span〉 〈span〉\(\Psi \)〈/span〉 〈/span〉: the first works only for 〈span〉 〈span〉\(\Psi 〈 \sqrt{3}\)〈/span〉 〈/span〉 and achieves 〈span〉 〈span〉\(Q(n) = O(1)\)〈/span〉 〈/span〉 with 〈span〉 〈span〉\(S(n) = O(n)\)〈/span〉 〈/span〉 and preprocessing time 〈span〉 〈span〉\(O(n\log n)\)〈/span〉 〈/span〉; the second data structure gives 〈span〉 〈span〉\(Q(n) = O(\Psi ^3 \sqrt{n})\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(\Psi ^3 n^{3/2})\)〈/span〉 〈/span〉; the third data structure is randomized with 〈span〉 〈span〉\(Q(n) = O(n^{2/3}\log ^{1/3} \Psi \log ^{2/3} n)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(n^{5/3}\log ^{1/3} \Psi \log ^{2/3} n)\)〈/span〉 〈/span〉 and answers queries correctly with high probability.〈/p〉