Loading...
Please wait, while we are loading the content...
Similar Documents
Time-Based Voronoi Diagram
| Content Provider | CiteSeerX |
|---|---|
| Author | Lee, D. T. Wang, Wei-Bung Liao, Chung-Shou |
| Abstract | We consider a variation of Voronoi diagram, or time-based Voronoi diagram, for a set S of points in the presence of transportation lines or highways in the plane. A shortest time-distance path from a query point to any given point in S is a path that takes the least travelling time. The travelling speeds and hence travelling times of the subpaths along the highways and in the plane are different. M. Abellanas et al. [1] gave a simple algorithm that runs in O(n log n) time, for computing the time-based Voronoi diagram for a set of n points in the presence of one highway in the plane. We consider a generalization of this problem to the case when there are two or more highways. We give a characterization of this problem and present an O(n log n) time algorithm for the problem where there are two highways. The algorithm can be easily extended to multiple highways if a certain intersection condition of highways holds. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Time-based Voronoi Diagram Shortest Time-distance Path Query Point Travelling Speed Certain Intersection Condition Transportation Line Simple Algorithm Voronoi Diagram Travelling Time Time Algorithm |
| Content Type | Text |
