Browsing by Author "Sysikaski, Mikko"

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.