ICS Theory Group

ICS 269, Winter 2002: Theory Seminar

7 Feb 2003:
Computing Homotopic Shortest Paths in the Plane
Yu Meng

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. We present two output-sensitive algorithms, for simple paths and non-simple paths.

(From a SODA 2003 paper by Sergei Bespamyatnikh.)