论文标题
有关传输图的可及性和距离甲骨文的注释
A Note on Reachability and Distance Oracles for Transmission Graphs
论文作者
论文摘要
让$ p $是飞机上的$ n $点的一组，其中每个点$ p \ in p $中的每个点$ p \都有变速箱半径$ r（p）> 0 $。由$ p $和给定的半径定义的传输图，由$ \ mathcal {g} _ {\ mathrm {tr}}}（p）$表示，是一个有向图，其节点是$ p $中的点，它包含arcs $（p，q）$ | pq | pq | \ leq leq r（p，p，p，p，q）$。 AN和OH [Algorithmica 2022]为传输图提供了可及的甲骨文。他们的Oracle使用$ o（n^{5/3}）$存储，并且给定两个查询点$ s，t \在p $中，可以在$ o（n^{2/3}）$ time中决定，如果有从$ s $到$ s $ in $ s $ in $ s in $ s in $ s in $ s $ s in $ \ mathcal {g nathcal {g} _ {g} _ {g} _ {\ mathrm {\ mathrm {tr}} $。我们表明，由de Berg \ emph {et al。}引入的基于集团的分离器可用于改善甲骨文的存储到$ O（n \ sqrt {n}）$以及查询时间到$ O（\ sqrt {n}）$。我们的甲骨文可以扩展到近似距离查询：我们可以为给定参数$ \ varepsilon> 0 $构造，一种使用$ o（（（n/\ varepsilon）\ sqrt {n} \ log n）$存储的甲骨文，并且可以在$ o（（\ sqrt n} n}/\ vareps $ fogs a pogiogs a）中$ d _ {\ mathrm {hop}}}^*（s，t）$满足$ d _ {\ mathrm {hop}}}（s，s，t）\ leq d _ {\ mathrm {hop}}}}^*（s，s，s，t） + 1 $，其中$ d _ {\ mathrm {hop}}}（s，t）$是从$ s $到$ t $的跳距。我们还展示了如何将Oracle扩展到所谓的连续查询，在该查询中，目标点$ t $可以是飞机中的任何点。 为了获得有效的预处理算法，我们表明，可以在$ o（n \ log n）$ time中构建一个基于集团的基于集团的分离器。
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 $\mathcal{G}_{\mathrm{tr}}(P)$, is the directed graph whose nodes are the points in $P$ and that contains the arcs $(p,q)$ such that $|pq|\leq 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 $\mathcal{G}_{\mathrm{tr}}(P)$. We show that the clique-based separators introduced by De Berg \emph{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 $\varepsilon>0$, an oracle that uses $O((n/\varepsilon)\sqrt{n}\log n)$ storage and that can report in $O((\sqrt{n}/\varepsilon)\log n)$ time a value $d_{\mathrm{hop}}^*(s,t)$ satisfying $d_{\mathrm{hop}}(s,t) \leq d_{\mathrm{hop}}^*(s,t) < (1+\varepsilon)\cdot d_{\mathrm{hop}}(s,t) + 1$, where $d_{\mathrm{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 $\Bbb{R}^d$ can be constructed in $O(n\log n)$ time.
