### Abstract

This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We give an exact algorithm for the basic version of the quickest path problem: given a transportation network with n edges in the Euclidean plane, a source point s ∈ R^{2} and a destination point t ∈ R^{2}, find the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n^{2} log n) into a data structure of size O(n^{2}=ε^{2}) such that (1 + ε)-approximate quickest path cost queries between any two points in the plane can be answered in time O(1=ε^{4} log n).

Original language | English |
---|---|

Title of host publication | Theory of Computing 2012 - Proceedings of the Eighteenth Computing |

Subtitle of host publication | The Australasian Theory Symposium, CATS 2012 |

Pages | 37-46 |

Number of pages | 10 |

Volume | 128 |

Publication status | Published - 24 Jul 2012 |

Event | Theory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012 - Melbourne, VIC, Australia Duration: 31 Jan 2012 → 3 Feb 2012 |

### Other

Other | Theory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012 |
---|---|

Country | Australia |

City | Melbourne, VIC |

Period | 31/01/12 → 3/02/12 |

### Fingerprint

### Cite this

*Theory of Computing 2012 - Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, CATS 2012*(Vol. 128, pp. 37-46)

}

*Theory of Computing 2012 - Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, CATS 2012.*vol. 128, pp. 37-46, Theory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012, Melbourne, VIC, Australia, 31/01/12.

**Quickest path queries on transportation network.** / Shawi, Radwa El; Gudmundsson, Joachim; Levcopoulos, Christos.

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

TY - GEN

T1 - Quickest path queries on transportation network

AU - Shawi, Radwa El

AU - Gudmundsson, Joachim

AU - Levcopoulos, Christos

PY - 2012/7/24

Y1 - 2012/7/24

N2 - This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We give an exact algorithm for the basic version of the quickest path problem: given a transportation network with n edges in the Euclidean plane, a source point s ∈ R2 and a destination point t ∈ R2, find the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n2 log n) into a data structure of size O(n2=ε2) such that (1 + ε)-approximate quickest path cost queries between any two points in the plane can be answered in time O(1=ε4 log n).

AB - This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We give an exact algorithm for the basic version of the quickest path problem: given a transportation network with n edges in the Euclidean plane, a source point s ∈ R2 and a destination point t ∈ R2, find the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n2 log n) into a data structure of size O(n2=ε2) such that (1 + ε)-approximate quickest path cost queries between any two points in the plane can be answered in time O(1=ε4 log n).

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

M3 - Conference contribution

SN - 9781921770098

VL - 128

SP - 37

EP - 46

BT - Theory of Computing 2012 - Proceedings of the Eighteenth Computing

ER -