Computing Transportation Voronoi Diagrams in Optimal Time
Yaron Ostrovsky-Berman · 2005
We present the first time-optimal algorithm for computing the Voronoi Diagram under the metric induced by a transportation network with discrete entry and exit points. For input with n sites, k stations, and e transportation lines, the algorithm computes the Voronoi Diagram in O ( (n + k) log(n + k)+e) time. 1 Introduction and related work Shortest Path Maps (SPM) and Voronoi Diagrams are well known geometric tools for answering distance related queries. The SPM is a subdivision of space, which allows finding the shortest path from a source