Geometric k Shortest Paths

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 k-th 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 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(k2m(m+ kn) log(kn)) time. We invite the reader to play with our applet demonstrating k-SPMs [10]