Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Efficient Computation of Jogging Routes

Andreas Gemsa, Thomas Pajor, Dorothea Wagner, and Tobias Zündorf

Abstract

We study the problem of computing jogging (running) routes in pedestrian networks: Given source vertex s and length L, it asks for a cycle (containing s) that approximates L while considering niceness criteria such as the surrounding area, shape of the route, and its complexity. Unfortunately, computing such routes is NP-hard, even if the only optimization goal is length. We therefore propose two heuristic solutions: The first incrementally extends the route by joining adjacent faces of the network. The other builds on partial shortest paths and is even able to compute sensible alternative routes. Our experimental study indicates that on realistic inputs we can compute jogging routes of excellent quality fast enough for interactive applications.

Details

Publication typeInproceedings
Published inProceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)
URLhttp://rd.springer.com/chapter/10.1007%2F978-3-642-38527-8_25
Pages272–283
Volume7933
SeriesLecture Notes in Computer Science
PublisherSpringer
> Publications > Efficient Computation of Jogging Routes