Problem: In a domain with polygonal boundaries, find the K shortest paths of different homotopy types between two points.

K = 1:

Problem: In a domain with polygonal boundaries, find the K shortest paths of different homotopy types between two points.

K = 2:

Problem: In a domain with polygonal boundaries, find the K shortest paths of different homotopy types between two points.

K = 3:

Use Dijkstra in "infinitesimally dense graph" on the domain

In practice, this is implemented by propagating circular wavefronts.

To find the K'th shortest paths we let colliding wavefronts continue, forming a "parking garage" structure:

K'th Shortest Path Map (K-SPM) is a subdivision of the polygonal domain such that:

• For all points in a region, the K'th shortest path is the same except for the last point.

Example of a 1-SPM:

Two types of boundaries in K-SPMs:

Changing homotopy type: Bisectors	Same homotopy type: Windows

After bisectors have been found, windows are easy to add.

In the garage algorithm, collision points of the wavefronts form the bisectors of the K-SPMs!

• It is already known that 1-SPM has O(n) complexity and it can be constructed in O(n log n) time and space.
• We are in process of proving that K-SPM has O(K^2 n) complexity
• The proof is based on analyzing on how the topological strucure of K-SPM depends on the topological structure of K-1-SPM.

Slides and visualization applet available in computational geometry group homepage!

http://www.cs.helsinki.fi/group/compgeom/