Voronoi Diagrams with a Transportation Network on the Euclidean Plane
Voronoi Diagrams with a Transportation Network on the Euclidean Plane
复制标题
欧几里得平面上的交通网络的 Voronoi 图
DOI：
10.1007/978-3-540-30551-4_11
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Kyung
中科院分区：
文献类型：
--
作者：
S. Bae;Kyung
本文研究了欧几里德平面上带运输网络的Voronoi图的几何性质和算法性质。对于一个交通网络，距离是用最短（时间）路径的长度来度量的。在这样做的时候，我们引入了一个针，一个广义的Voronoi站点。本文提出了一个O（nm2logn+m3logm）算法来计算欧氏平面上交通网络的Voronoi图，其中n是给定站点的个数，m是给定交通网络的复杂度.
This paper investigates geometric and algorithmic properties of the Voronoi diagram with a transportation network on the Euclidean plane. With 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 anO(nm2logn+m3logm) algorithm to compute the Voronoi diagram with a transportation network on the Euclidean plane, wherenis the number of given sites andmis the complexity of the given transportation network.