Computing minimum length paths of a given homotopy class (Q1330462)

It is shown how the notion of the universal covering space of a triangulated region can be used as a unifying framework to compute paths under various metrics in a simple polygon. Shortest paths and shortest closed curves under Euclidean and link metrics and paths that are restricted to use \(c\) given orientations are considered and new algorithms for computing minimum length and minimum link \(c\)-oriented paths are given. Also algorithms using simple arrays and stacks instead of more complicated data structures used in previously known algorithms for Euclidean shortest path trees and minimum-link paths are given.