Approximate shortest path queries in graphs using Voronoi duals

Shinichi Honiden; Michael E. Houle; Christian Sommer; Martin Wolff

doi:10.1109/ISVD.2009.30

Approximate shortest path queries in graphs using Voronoi duals

Shinichi Honiden^*, Michael E. Houle, Christian Sommer, Martin Wolff

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009
Pages	53-62
Number of pages	10
DOIs	https://doi.org/10.1109/ISVD.2009.30
Publication status	Published - 2009 Dec 1
Externally published	Yes
Event	6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009 - Copenhagen, Denmark Duration: 2009 Jun 23 → 2009 Jun 26

Publication series

Name	6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009

Other

Other	6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009
Country/Territory	Denmark
City	Copenhagen
Period	09/6/23 → 09/6/26

Keywords

Approximation
Distance oracle
Graph Voronoi diagram
Shortest path

ASJC Scopus subject areas

Information Systems
Biomedical Engineering
Applied Mathematics

Access to Document

10.1109/ISVD.2009.30

Cite this

Approximate shortest path queries in graphs using Voronoi duals. / Honiden, Shinichi; Houle, Michael E.; Sommer, Christian et al.
6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009. 2009. p. 53-62 5362417 (6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Honiden, S, Houle, ME, Sommer, C & Wolff, M 2009, Approximate shortest path queries in graphs using Voronoi duals. in 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009., 5362417, 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009, pp. 53-62, 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009, Copenhagen, Denmark, 09/6/23. https://doi.org/10.1109/ISVD.2009.30

@inproceedings{b060cd3313cd4dadb166853275862648,

title = "Approximate shortest path queries in graphs using Voronoi duals",

abstract = "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.",

keywords = "Approximation, Distance oracle, Graph Voronoi diagram, Shortest path",

author = "Shinichi Honiden and Houle, {Michael E.} and Christian Sommer and Martin Wolff",

year = "2009",

month = dec,

day = "1",

doi = "10.1109/ISVD.2009.30",

language = "English",

isbn = "9780769537818",

series = "6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009",

pages = "53--62",

booktitle = "6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009",

note = "6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009 ; Conference date: 23-06-2009 Through 26-06-2009",

}

TY - GEN

T1 - Approximate shortest path queries in graphs using Voronoi duals

AU - Honiden, Shinichi

AU - Houle, Michael E.

AU - Sommer, Christian

AU - Wolff, Martin

PY - 2009/12/1

Y1 - 2009/12/1

N2 - 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.

AB - 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.

KW - Approximation

KW - Distance oracle

KW - Graph Voronoi diagram

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=77951493159&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951493159&partnerID=8YFLogxK

U2 - 10.1109/ISVD.2009.30

DO - 10.1109/ISVD.2009.30

M3 - Conference contribution

AN - SCOPUS:77951493159

SN - 9780769537818

T3 - 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009

SP - 53

EP - 62

BT - 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009

T2 - 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009

Y2 - 23 June 2009 through 26 June 2009

ER -

Approximate shortest path queries in graphs using Voronoi duals

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this