Geometric k shortest paths

Creative Commons License

Eriksson-Bique S., Hershberger J., Polishchuk V., Speckii B., Suri S., Talvitie T., ...More

26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, California, United States Of America, 4 - 06 January 2015, vol.2015-January, pp.1616-1625 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 2015-January
  • Doi Number: 10.1137/1.9781611973730.107
  • City: California
  • Country: United States Of America
  • Page Numbers: pp.1616-1625
  • Middle East Technical University Affiliated: No


Copyright © 2015 by the Society for Industrial and Applied Mathmatics.We consider the problem of computing k shortest paths in a two-dimensional environment with polygonal obstacles, where the jth path, for 1 ≤ j ≤ k, is the shortest path in the free space that is also homotopically distinct from each of the first j-1 paths. In fact, we consider a more general problem: given a source point s, construct a partition of the free space, called the kth shortest path map (k-SPM), in which the homotopy of the kth shortest path in a region has the same structure. Our main combinatorial result establishes a tight bound of θ (k2h + kn) on the worst-case complexity of this map. We also describe an O ( (k3h + k2n) log (kn)) time algorithm for constructing the map. In fact, the algorithm constructs the jth map for every j ≤ k. Finally, we present a simple visibility-based algorithm for computing the k shortest paths between two fixed points. This algorithm runs in O (m log n + k) time and uses O (m + k) space, where to is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O (k2m (m + kn) log (fcn)) time. We invite the reader to play with our applet demonstrating fc-SPMs [10].