Name
Abstract | ||
|---|---|---|
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(nm(2) + m(3) + 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 + m(2) + n log n) time with O(m(n + m)) space and the other O(nm log n + m(2) log M) time with O(n + m) space. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1142/S0218195906001963 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
transportation network, time metric, Voronoi diagram, shortest path | Journal | 16 |
Issue | ISSN | Citations |
2-3 | 0218-1959 | 9 |
PageRank | References | Authors |
0.66 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sang Won Bae | 1 | 189 | 31.53 |
| Kyung-Yong Chwa | 2 | 919 | 97.10 |