Voronoi Diagrams for a Transportation Network on the Euclidean Plane
Voronoi Diagrams for a Transportation Network on the Euclidean Plane
复制标题
欧几里得平面上交通网络的 Voronoi 图
DOI：
10.1142/s0218195906001963
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Kyung
中科院分区：
文献类型：
--
作者：
S. Bae;Kyung
本文研究了欧几里得平面上交通网络的Voronoi图的几何性质和算法性质。在存在交通网络的情况下，距离是以最短（时间）路径的长度来衡量的。在这样做的过程中，我们引入了一根针，一个广义的沃罗诺伊位点。我们提出了一种O（nm2 + m3 + nm log n）算法来计算欧几里得平面上运输网络的Voronoi图，其中n是给定站点的数量，m是给定运输网络的复杂性。此外，在交通网络中的道路只有恒定数量的方向和速度的情况下，我们提出了两种算法；一个需要O（nm + m2 + n log n）时间和O（m(n + m)）空间，另一个需要O（nm log n + m2log m）时间和O（n + m）空间。
This paper investigates geometric and algorithmic properties of the Voronoi diagram for a transportation network on the Euclidean plane. In the presence of a transportation network, the distance is measured as the length of the shortest (time) path. In doing so, we introduce a needle, a generalized Voronoi site. We present an O(nm2 + m3 + nm log n) algorithm to compute the Voronoi diagram for a transportation network on the Euclidean plane, where n is the number of given sites and m is the complexity of the given transportation network. Moreover, in the case that the roads in a transportation network have only a constant number of directions and speeds, we propose two algorithms; one needs O(nm + m2 + n log n) time with O(m(n + m)) space and the other O(nm log n + m2log m) time with O(n + m) space.