A Note on Reachability and Distance Oracles for Transmission Graphs

2025-04-27 0 0 655.22KB 14 页 10玖币
侵权投诉
A Note on Reachability and Distance Oracles for
Transmission Graphs
Mark de Berg !
Department of Mathematics and Computer Science, TU Eindhoven, the Netherlands
Abstract
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 Pand 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/ε
)
√nlog n
)storage and that can report in
O
((
√n/ε
)
log n
)time a value
d∗
hop
(
s, t
)satisfying
dhop
(
s, t
)
⩽d∗
hop
(
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 tcan 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 Rdcan be constructed in O(nlog n)time.
2012 ACM Subject Classification Theory of computation →Design and analysis of algorithms
Keywords and phrases
Computational geometry, transmission graphs, reachability oracles, approximate
distance oracles, clique-based separators
Funding
MdB is supported by the Dutch Research Council (NWO) through Gravitation-grant
NETWORKS-024.002.003.
1 Introduction
Let
P
be a set of
n
points in the plane, where each point
p∈P
has an associated 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 an arc (
p, q
)between
two points
p, q ∈P
if and only if
|pq|⩽r
(
p
), where
|pq|
denotes the Euclidean distance
between
p
and
q
. Transmission graphs are a popular way to model wireless communication
networks.
The study of transmission graphs leads to various challenging algorithmic problems. In
this paper we are interested in so-called reachability queries: given two query points
s, t ∈P
,
is there a path
1
from
s
to
t
in
Gtr
(
P
)? A closely related query asks for the hop-distance from
s
to
t
, which is the minimum number of arcs on any path from
s
to
t
. Reachability queries
can be answered in
O
(1) time if we precompute for every pair
p, q ∈P
whether or not
q
is
reachable from
p
and then store that information in a two-dimensional array. This requires
quadratic storage. Our goal is to develop a structure using subquadratic storage that allows
us to quickly answer reachability queries. Such a data structure is called a reachability oracle.
If the data structure can also report the (approximate) hop-distance from
s
to
t
then it is
called an (approximate) distance oracle.
1Whenever we speak about paths in Gtr(P), we always mean directed paths.
arXiv:2210.05788v1 [cs.CG] 11 Oct 2022
2 A Note on Reachability and Distance Oracles for Transmission Graphs
Note that reachability queries for an undirected graph
G
can be trivially answered in
O
(1) time after computing the connected components of
G
. For directed graphs, however,
efficient reachability oracles are much harder to design. In fact, for arbitrary directed graphs
one cannot hope for an oracle that uses subquadratic storage. To see this, consider the class
of directed bipartite graphs
G
= (
V∪W, E
)with
|V|
=
|W|
=
n/
2. Then any reachability
oracle must use Ω(
n2
)bits of storage in the worst case, otherwise two different graphs will
end up with the same encoding and the oracle cannot answer all queries correctly on both
graphs. Surprisingly, even for sparse directed graphs no reachability oracles are known that
use subquadratic storage and have sublinear query time. Directed planar graphs, on the other
hand, admit very efficient reachability oracles: almost three decades of research [
4
,
5
,
7
,
8
]
eventually resulted in the optimal solution by Holm, Rotenberg and Thorup [
13
], who
presented an oracle that has
O
(
n
)storage and
O
(1) query time. Moreover, there are various
(approximate) distance oracles for directed planar graphs; see for example [
11
,
16
,
21
] and
the references therein.
Planar graphs are sparse, but transmission graphs can be dense. Nevertheless, the
geometric structure of transmission graphs makes it possible to beat the quadratic lower
bound on the amount of storage. Kaplan et al. [
15
] presented three reachability oracles for
transmission graphs. Their oracles use subquadratic storage when Ψ, the ratio between
the largest and smallest transmission radius, is sufficiently small. The first oracle has
excellent performance—it uses
O
(
n
)storage and can answer queries in
O
(1) time—but it
only works when Ψ
<√3
. The second oracle works for any Ψ, but it uses
O
(Ψ
3n√n
)
storage and has
O
(Ψ
3√n
)query time. The third oracle has a reduced dependency on Ψ—it
has
O
((
log1/3
Ψ)
·n5/3log2/3n
)storage and
O
((
log1/3
Ψ)
·n2/3log2/3n
)query time—but an
increased dependency on
n
. This third structure is randomized and answers queries correctly
with high probability. Recently, An and Oh [
3
] presented the first reachability oracle that
has subquadratic storage independent of Ψ. It uses
O
(
n5/3
)storage and has
O
(
n2/3
)query
time. They also presented an oracle that uses
O
(
n√nlog Ψ
)storage and has
O
(
√nlog Ψ
)
query time.
Our contribution and technique.
We present a reachability oracle for transmission graphs
that uses
O
(
n√n
)storage and has
O
(
√n
)query time. This significantly improves both
the storage and the query time of the oracle presented by An and Oh [
3
]. Our oracle
uses a divide-and-conquer approach based on separators. This is a standard approach for
reachability oracles—it goes back to (at least) the work of Arikati et al. [
4
] and is also used
by Kaplan et al. and by An and Oh. It works as follows.
Consider a directed graph
G
= (
V, E
)and let
S⊂V
be a separator for
G
. Thus
V\S
can be partitioned into two parts
A, B
of roughly equal size such that there are no arcs
between
A
and
B
. The oracle now stores for each pair of nodes (
u, v
)
∈V×S
whether
u
can
reach
v
in
G
, and whether
v
can reach
u
in
G
. In addition, there are recursively constructed
oracles for the subgraphs
G
[
A
]and
G
[
B
]induced by
A
and
B
, respectively. Answering a
reachability query with vertices
s, t
can then be done as follows: we first check if
s
can reach
t
via a node in
S
, that is, if there is a node
v∈S
such that
s
can reach
v
and
v
can reach
t
.
Using the precomputed information this takes
O
(
|S|
)time. If
s
can reach
t
via a node in
S
,
we are done. Otherwise,
s
can only reach
t
if
s
and
t
lie in the same part of the partition,
say A, and scan reach tin G[A]. This can be checked recursively.
For graph classes that admit a separator of size
s
(
n
), where
n
:=
|V|
, this approach leads
to an oracle with
O
(
n·s
(
n
)) storage and
O
(
s
(
n
)) query time, assuming
s
(
n
) = Ω(
nα
)for
some
α >
0. The problem when using this approach for transmission graphs is that they
M. de Berg 3
may not have separators of sublinear size. An and Oh [
3
] therefore apply the following
preprocessing step. Let
DP
be the set of disks defined by the points in
P
and their ranges.
Then An and Oh iteratively remove collections of Ω(
n1/3
)disks that contain a common
point. Note that the disks in such a collection form a clique in the intersection graph defined
by
DP
. For each collection
C
, a structure is built to check for two query points
s, t ∈P
if
s
can reach
t
via a point corresponding to a disk in
C
. The set of disks remaining after
this preprocessing step has ply
O
(
n1/3
)—any point in the plane is contained in
O
(
n1/3
)
of them. This implies that the corresponding transmission graph admits a separator of
size
O
(
n2/3
)[
18
,
19
], leading to a reachability oracle with
O
(
n5/3
)storage and
O
(
n2/3
)query
time.
2
Our main insight is that we can use the so-called clique-based separators recently
developed by De Berg et al. [
6
]. (A clique-based separator for a graph
G
is a separator that
consists of a small number of cliques, rather than a small number of nodes.) This allows
use to avoid An and Oh’s preprocessing step and integrate the handling of cliques into the
global separator approach, giving an oracle with O(n√n)storage and O(√n)query time.
We also show how to adapt the oracle such that it can answer approximate hop-distance
queries. In particular, we show how to construct, for a given parameter
ε >
0, an approximate
distance oracle that uses
O
((
n/ε
)
√nlog n
)storage. The oracle can report, for two query
points
s, t ∈P
, a value
d∗
hop
(
s, t
)satisfying
dhop
(
s, t
)
⩽d∗
hop
(
s, t
)
<
(1+
ε
)
·dhop
(
s, t
)+1, where
dhop
(
s, t
)denotes the hop-distance from
s
to
t
in
Gtr
(
P
). The query time is
O
((
√n/ε
)
log n
).
Finally, we study so-called continuous reachability queries, where the target point
t
can
be any point in
R2
. Such a query asks, for a query pair
s, t ∈P×R2
, if there is a point
q∈P
with
|qt|⩽r
(
q
)such that
s
can reach
q
. Kaplan et al. [
15
] presented a data structure
using
O
(
nlog
Ψ) storage such that any reachability oracle can be extended to continuous
reachability queries
3
with an additive overhead of
O
(
log nlog
Ψ) to the query time. An
and Oh [
3
] also extended their reachability oracle to continuous reachability queries. The
storage of their oracle remained the same, namely
O
(
n5/3
), but the query increased by a
multiplicative polylogarithmic factor to
O
(
n2/3log2n
). We present a new data structure to
extend any reachability oracle to continuous queries. It uses
O
(
nlog n
)storage and has an
additive overhead of
O
(
log2n
)to the query time. Thus, unlike the method of Kaplan et al.,
its performance is independent of the ratio Ψ, and unlike the method of An and Oh, we
do not incur a penalty on the query time when combined with our reachability oracle: the
total query time remains
O
(
√n
)and the total storage remains
O
(
n√n
). The extension to
continuous queries also applies to approximate distance queries, with an additional additive
error of a single hop.
To construct our oracles, we need an algorithm to construct a clique-based separator for
the intersection graph
G×
(
D
)of a set
D
of
n
disks in the plane. De Berg et al. [
6
] present a
brute-force construction algorithm for the case where
D
is a set of convex fat objects in
Rd
,
running in
O
(
nd+2
)time. This is sufficient for their purposes, since they use the separator
to develop sub-exponential algorithms. For us the separator construction would become the
bottleneck in our preprocessing algorithm. Before presenting our oracles, we therefore first
show how to construct the clique-based separator in
O
(
nlog n
)time. Since we expect that
clique-based separators will find more applications where the construction time is relevant,
we believe this result is of independent interest.
2
Actually, this preprocessing needs to be done at each step in the recursive construction of the oracle.
Otherwise the ply would be
O
(
n2/3
0
)instead of
O
(
n1/3
), where
n0
is the initial number of points and
n
is the number of points in the current recursive call, resulting in an extra logarithmic factor in storage.
3Kaplan et al. used the term geometric reachability queries.
摘要：

ANoteonReachabilityandDistanceOraclesforTransmissionGraphsMarkdeBerg!DepartmentofMathematicsandComputerScience,TUEindhoven,theNetherlandsAbstractLetPbeasetofnpointsintheplane,whereeachpointp∈Phasatransmissionradiusr(p)>0.ThetransmissiongraphdefinedbyPandthegivenradii,denotedbyGtr(P),isthedirectedgra...

展开>> 收起<<
A Note on Reachability and Distance Oracles for Transmission Graphs.pdf

共14页,预览3页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：14 页 大小：655.22KB 格式：PDF 时间：2025-04-27

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 14
评分 收藏
分享
立即下载
客服
关注