Rectilinear shortest paths among weighted rectilinear obstacles
Tsung-Hsu Chen, Der-Tsai Lee · 1989
In this dissertation, we study the rectilinear shortest path problems among rectilinear obstacles. A weighted obstacle represents a region through which an extra cost will be incurred and the shortest path between two distinguished points in the presence of weighted obstacles is the one with minimum total cost. By using the plane sweep approach, we obtain an algorithm to solve the problem when the obstacles are weighted rectangles. The algorithm runs in $\Theta (n \log n)$ time and uses $\Theta (n)$ space where $n$ is the number of the vertices of obstacles. By using a graph-theoretical approach, the problem with weighted rectilinear obstacles can be solved in \log\sp2 n)$ time and \log N)$ space. After adjusting the graph, an algorithm which runs in $O(n \log\sp{3/2} n)$ time and space is also presented. A useful scheme named weighted segment tree, which is believed to be helpful in other situations, plays an important role of reducing the time complexity in the above problems.