Euclidean shortest paths in the presence of rectilinear barriers 论文

摘要

Abstract In this paper we address the problem of constructing a Euclidean shortest path between two specified points (source, destination) in the plane, which avoids a given set of barriers. This problem had been solved earlier for polygonal obstacles with the aid of the visibility graph. This approach however, has an Ω(n 2 ) time lower bound, if n is the total number of vertices of the obstacles. Our goal is to find interesting cases for which the solution can be obtained without the explicit construction of the entire visibility graph. The two cases are (i) the path must lie within an n‐vertex simple polygon; (ii) the obstacles are n disjoint and parallel line segments. In both instances greedy O(n log n) time algorithms can be developed which solve the problems by constructing the shortest‐path tree from the source to all the vertices of the obstacles and to the destination.