Efficient Computation of Jogging Routes

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.

In  Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)

Publisher  Springer

Details

TypeInproceedings
URLhttp://rd.springer.com/chapter/10.1007%2F978-3-642-38527-8_25
Pages272–283
Volume7933
SeriesLecture Notes in Computer Science
> Publications > Efficient Computation of Jogging Routes