Skip to main content
Login | Suomeksi | På svenska | In English

Geometric kth shortest paths

Show simple item record 2015-11-25T12:50:48Z und 2017-10-24T12:21:49Z 2015-11-25T12:50:48Z und 2017-10-24T12:21:49Z 2015-11-25T12:50:48Z
dc.identifier.uri und
dc.title Geometric kth shortest paths en
ethesis.discipline Applied Mathematics en
ethesis.discipline Soveltava matematiikka fi
ethesis.discipline Tillämpad matematik sv
ethesis.department Institutionen för matematik och statistik sv
ethesis.department Department of Mathematics and Statistics en
ethesis.department Matematiikan ja tilastotieteen laitos fi
ethesis.faculty Matematisk-naturvetenskapliga fakulteten sv
ethesis.faculty Matemaattis-luonnontieteellinen tiedekunta fi
ethesis.faculty Faculty of Science en
ethesis.faculty.URI Helsingfors universitet sv University of Helsinki en Helsingin yliopisto fi
dct.creator Talvitie, Topi
dct.issued 2015
dct.language.ISO639-2 eng
dct.abstract 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. en
dct.subject computational geometry en
dct.subject locally shortest paths en
dct.subject route planning en
dct.language en
ethesis.language English en
ethesis.language englanti fi
ethesis.language engelska sv
ethesis.thesistype pro gradu-avhandlingar sv
ethesis.thesistype pro gradu -tutkielmat fi
ethesis.thesistype master's thesis en
dct.identifier.urn URN:NBN:fi:hulib-201711155703
dc.type.dcmitype Text

Files in this item

Files Size Format View
gradu.pdf 1.180Mb PDF

This item appears in the following Collection(s)

Show simple item record