Optimal Construction of the City Voronoi Diagram
Optimal Construction of the City Voronoi Diagram
复制标题
城市Voronoi图的优化构建
DOI：
10.1142/s021819590900285x
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Kyung
中科院分区：
文献类型：
--
作者：
S. Bae;Jae;Kyung
我们解决的L1平面上的道路存在的邻近问题。更具体地说，我们提出了第一个最优算法构建城市Voronoi图。我们应用连续Dijkstra方法得到一个最优算法，建立一个给定的源的最短路径图，然后它扩展到城市Voronoi图。此外，我们的算法可以扩展到其他广义的情况，包括度量空间的道路和障碍物一起诱导。
We address proximity problems in the presence of roads on the L1 plane. More specifically, we present the first optimal algorithm for constructing the city Voronoi diagram. We apply the continuous Dijkstra method to obtain an optimal algorithm for building a shortest path map for a given source, and then it extends to that for the city Voronoi diagram. Moreover, our algorithm can be extended to other generalized situations including metric spaces induced by roads and obstacles together.