Rectilinear link diameter and radius in a rectilinear polygonal domain
Rectilinear link diameter and radius in a rectilinear polygonal domain
复制标题
直线多边形域中的直线链接直径和半径
DOI：
10.1016/j.comgeo.2020.101685
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Roeloffzen Marcel
中科院分区：
文献类型：
--
作者：
Arseneva Elena;Chiu Man-Kwun;Korman Matias;Markovic Aleksandar;Okamoto Yoshio;Ooms Aur?lien;van Renssen Andr?;Roeloffzen Marcel
我们研究了n个顶点和h个孔的直线多边形域内直线链接距离下的直径和半径的计算。我们引入了定向距离图来编码域中点对之间的距离。这有助于我们转变问题，以便我们可以更有效地搜索候选人。我们的算法在 O (min(n ω, n 2+ n h log h+ χ 2)) 时间内计算直径和半径，其中 ω< 2.373 表示矩阵乘法指数，χ∈ Ω (n)∩ O (n 2) 是定向距离图的边数。我们还提供了一种计算直径的替代算法，该算法在 O (n 2 log n) 时间内运行。
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O (min(n ω, n 2+ n h log h+ χ 2)) time, where ω< 2.373 denotes the matrix multiplication exponent and χ∈ Ω (n)∩ O (n 2) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O (n 2 log n) time.