Computing minimum length paths of a given homotopy class (Q1330462)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computing minimum length paths of a given homotopy class |
scientific article |
Statements
Computing minimum length paths of a given homotopy class (English)
0 references
21 July 1994
0 references
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.
0 references
universal covering space
0 references
Euclidean shortest path trees
0 references
minimum-link paths
0 references
0 references
0 references
