Winter 2015: Theory Seminar
ICS, Room 243, 1:00pm
February 13, 2015:

Geometric $k$-Shortest Paths

Tim Johnson

We consider the problem of computing $k$ shortest paths in a two-dimensional environment with polygonal obstacles, where the $j$th path, for $j$ in $[1,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 $k$ shortest paths in a region has the same structure.

This is a paper from SODA 2015 by Sylvester Eriksson-Bique, John Hershberger, Valentin Polishchuk, Bettina Speckmann, Subhash Suri, Topi Talvitie, Kevin Verbeekk, and Hakan Yildiz