Abstract
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 T(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 m is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O(k2 m(m + kn) log (kn)) time.
We invite the reader to play with our applet demonstrating k-SPMs [10].
Original language | English |
---|---|
Title of host publication | Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15, San Diego CA, USA, January 4-6, 2015) |
Place of Publication | Philadelpia |
Publisher | Society for Industrial and Applied Mathematics (SIAM) |
Pages | 1616-1625 |
ISBN (Print) | 978-1-61197-374-7 |
DOIs | |
Publication status | Published - 2015 |
Event | 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) - Westin San Diego Gaslamp Quarter, San Diego, United States Duration: 4 Jan 2015 → 6 Jan 2015 Conference number: 26 http://www.siam.org/meetings/da15/ |
Conference
Conference | 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) |
---|---|
Abbreviated title | SODA '15 |
Country/Territory | United States |
City | San Diego |
Period | 4/01/15 → 6/01/15 |
Other | Event co-located with the 17th Workshop on Algorithm Engineering and Experiments (ALENEX '15) and the 12th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '15) |
Internet address |