1. VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE.
- Author
-
Sang Won Bae and Kyung-Yong Chwa
- Subjects
- *
VORONOI polygons , *GRAPHIC methods , *CHRONOMETERS , *ALGORITHMS , *TRANSPORTATION , *ANALYTIC spaces - 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(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. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF