Rectilinear minimum link paths in two and higher dimensions

Show full item record

Title: Rectilinear minimum link paths in two and higher dimensions
Author: Sysikaski, Mikko
Contributor: University of Helsinki, Faculty of Science
Publisher: Helsingin yliopisto
Date: 2019
Thesis level: master's thesis
Abstract: The thesis discusses algorithms for the minimum link path problem, which is a well known geometric path finding problem. The goal is to find a path that does the minimum number of turns amidst obstacles in a continuous space. We focus on the most classical variant, the rectilinear minimum link path problem, where the path and the obstacles are restricted to the directions of the coordinate axes. We study the rectilinear minimum link path problem in the plane and in the three-dimensional space, as well as in higher dimensional domains. We present several new algorithms for solving the problem in domains of varying dimension. For the planar case we develop a simple method that has the optimal O(n log n) time complexity. For three-dimensional domains we present a new algorithm with running time O(n^2 log^2 n), which is an improvement over the best previously known result O(n^2.5 log n). The algorithm can also be generalized to higher dimensions, leading to an O(n^(D-1) log^(D-1) n) time algorithm in D-dimensional domains. We describe the new algorithms as well as the data structures used. The algorithms work by maintaining a reachable region that is gradually expanded to form a shortest path map from the starting point. The algorithms rely on several efficient data structures: the reachable region is tracked by using a simple recursive space decomposition, and the region is expanded by a sweep plane method that uses a multidimensional segment tree.
Discipline: Tietojenkäsittelytiede

Files in this item

Total number of downloads: Loading...

Files Size Format View
Sysikaski_Mikko_Pro_gradu_2019.pdf 743.1Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record