Browsing by Author "Talvitie, Topi"

Finding shortest paths in planar domains bounded by polygons is a well-studied problem in computational geometry. However, in many applications, only finding the shortest path is not sufficient: we need to be able to generate a list of short paths among which we can choose the route. Simple detours to the shortest path are rarely better than the direct path, and therefore we should return paths that are essentially different. To ensure that, we limit our consideration to locally shortest paths, defined as the paths that cannot be made shorter by infinitesimal perturbations, or more intuitively, the paths that are 'pulled taut' around the obstacles of the domain. We use the first half of the thesis to present the definitions and the basic theory of locally shortest paths. We prove that they are always polygonal chains of certain type, and use this to describe a simple visibility graph based algorithm for finding the kth shortest path, i.e. the kth element in the list of locally shortest paths between given points ordered by length. We prove that there is a unique way to change a locally shortest path continuously by moving its endpoints while keeping the path locally shortest. This result is used to show that the set of locally shortest paths with one fixed endpoint forms a covering space of the planar domain. We use this to to prove a connection between homotopy theory and locally shortest paths: each homotopy class contains exactly one locally shortest path, and that path is the shortest path in its homotopy class. The covering space structure formed by locally shortest paths also gives rise to the idea of tracking the lengths of the locally shortest paths between a fixed point s and a point x, and drawing a map of the points x in which the order of lengths of the paths changes or the type of one of the locally shortest paths changes. The resulting map is the kth shortest path map, a subdivision of the domain into components such that the kth shortest path from s to any point within a single component is essentially the same. We analyze the structure and complexity of this map, concluding that we can use it for efficient queries of kth shortest paths from s to any point x.