Approximate Shortest Path Queries Using Voronoi Duals

Shinichi Honiden, Michael E. Houle, Christian Sommer, and Martin Wolff
Transactions on Computational Science, Volume IX, Special Issue for the 6th International Symposium on Voronoi Diagrams in Science and Engineering, LNCS 6290 (pp. 28-53), 2010

We propose an approximation method to answer point-to-point shortest path queries in undirected graphs, based on random sampling and Voronoi duals. We compute a simplification of the graph by selecting nodes independently at random with probability p. Edges are generated as the Voronoi dual of the original graph, using the selected nodes as Voronoi sites. This overlay graph allows for fast computation of approximate shortest paths for general, undirected graphs. The time-quality tradeoff decision can be made at query time. We provide bounds on the approximation ratio of the path lengths as well as experimental results. The theoretical worst-case approximation ratio is bounded by a logarithmic factor. Experiments show that our approximation method based on Voronoi duals has extremely fast preprocessing time and efficiently computes reasonably short paths.

@article{HHSW10,
 author  = {Shinichi Honiden 
              and Michael E. Houle 
              and Christian Sommer 
              and Martin Wolff},
 title   = {Approximate Shortest Path Queries 
            in Graphs Using Voronoi Duals},
 journal = {Transactions on Computational Science},
 volume  = {9},
 year    = {2010},
 pages   = {28--53},
 url     = {http://dx.doi.org/10.1007/978-3-642-16007-3_2},
 doi     = {10.1007/978-3-642-16007-3_2},
 note    = {Special Issue of the 6th International 
            Symposium on Voronoi Diagrams in 
            Science and Engineering (ISVD 2009)}
}

Official version
Local version (415.4 KB)

Travel agencies or producers of navigation systems may wish to provide advice to clients, who want to know the shortest, fastest, or cheapest way from one point to another. Instead of searching a large part of a transportation map using a traditional algorithm at every client query, they could instead precompute certain information in order to better support subsequent queries. In our research, we design, analyze, and implement a method - based on random sampling and graph Voronoi duals - that precomputes this information so as to obtain fast, approximate answers for point-to-point shortest path queries in undirected graphs.

See also Balancing Graph Voronoi Diagrams.

Home → Publications → Approximate Shortest Path Queries Using Voronoi Duals