Algorithms for shortest paths and visibility polygons in r2
Sanjiv Kapoor, R. Inkulu · 2007
The Euclidean Shortest Path problem in R 2 can be stated as - given a collection of obstacles, find a Euclidean shortest obstacle-avoiding path between two given points. This fundamental problem is listed as part of The Open Problems Project (TOPP) of Computational Geometry. This research provides an algorithm with O( n + m lg2 n) time and O( n) space. Throughout the thesis, n represents the number of vertices in the given polygonal region with obstacles, m is the number of obstacles, and, O(T) is the time to triangulate the polygonal region which is of O( n + m lg1+e m) (for a small positive constant e). The bound achieved is close to the lower bound of Ω(n + m lg m). The Rectilinear Shortest Path problem requires finding a shortest path with rectilinear (L1) metric such that the shortest path does not intersect with any of the m non-intersecting obstacles in the given polygonal region. The solution provided in this thesis gives an algorithm with time complexity O( T + m(lg n)3/2), which is close to the lower bound of Ω(n + m lg m). The Weighted Euclidean Shortest Path problem in R2 can be described as - find an Euclidean shortest path from a source s to a sink t in the polygonal region where the obstacles are associated with weights. Unlike the last two problems, the shortest path is allowed to traverse across the weighted obstacles in the polygonal region. We present an algorithm with O (n6 lg pKe'p + n5 + n4 lg pWwe'p ) time complexity. Here e' = ecnpn2+LWp , K is a constant, cn is the number of vertices, w is the minimum weight, W is the maximum weight, and L is the maximum length of any edge. Our algorithm time complexity is better than any polynomial time algorithm, and, it is better than any known pseudo-polynomial time algorithm whenever N2e > n5. Further, we present an output-sensitive algorithm for finding the Visibility Polygon of a query point located inside a given polygonal region with polygonal holes. We provide two bounds on the complexity of this problem. One approach constructs a data structure with space complexity O(n2) with pre-processing time O(n2) and yields a query time of O((1 + min(m, |V( q)|)) lg2 n + m + |V( q)|). Here, V(q) represents the set of vertices of the visibility polygon of a query point q, |E| denotes the number of edges in the visibility graph. The other approach provides a data structure with space complexity O(min(|E|, mn) + n) and pre-processing time O( T + |E| + n lg n) with the query time of O(|V(q)| lg n + m). The preprocessing time and space of our algorithm using either of these approaches improves upon the existing algorithms. The query time is competitive with the previous methods when there are either a small constant number of holes or |V(q)| ≥ m. In both of these approaches, with the additional O(( min(|E|, mn))2) space both the space and query complexities found to be superior and competitive respectively to previous methods whenever n > m 2.