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

Geometric kth shortest paths

Show simple item record

dc.date.accessioned 2015-11-25T12:50:48Z und
dc.date.accessioned 2017-10-24T12:21:49Z
dc.date.available 2015-11-25T12:50:48Z und
dc.date.available 2017-10-24T12:21:49Z
dc.date.issued 2015-11-25T12:50:48Z
dc.identifier.uri http://radr.hulib.helsinki.fi/handle/10138.1/5161 und
dc.identifier.uri http://hdl.handle.net/10138.1/5161
dc.title Geometric kth shortest paths en
ethesis.discipline Applied Mathematics en
ethesis.discipline Soveltava matematiikka fi
ethesis.discipline Tillämpad matematik sv
ethesis.discipline.URI http://data.hulib.helsinki.fi/id/2646f59d-c072-44e7-b1c1-4e4b8b798323
ethesis.department.URI http://data.hulib.helsinki.fi/id/61364eb4-647a-40e2-8539-11c5c0af8dc2
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 http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca
ethesis.university.URI http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97
ethesis.university Helsingfors universitet sv
ethesis.university University of Helsinki en
ethesis.university 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.URI http://data.hulib.helsinki.fi/id/languages/eng
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
ethesis.thesistype.URI http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis
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