Finding a Rectilinear Shortest Path in R2 Using Corridor Based Staircase Structures
The rectilinear shortest path problem can be stated as - given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest rectilinear (L 1) path from a point s to a point t which avoids all the obstacles. The path can touch an ob
- PDF / 484,976 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 3 Downloads / 209 Views
Abstract. The rectilinear shortest path problem can be stated as - given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest rectilinear (L1 ) path from a point s to a point t which avoids all the obstacles. The path can touch an obstacle but does not cross it. This paper presents an algorithm with time complexity O(n + m(lg n)3/2 ), which is close to the known lower bound of Ω(n + m lg m) for finding such a path. Here, n is the number of vertices of all the obstacles together. Our algorithm is of O(n + m(lg m)3/2 ) space complexity.
1
Introduction
In this paper, we are interested in finding a 2-dimensional rectilinear (L1 ) shortest path from a point s to another point t in a polygonal region P comprising m non-intersecting polygoinal obstacles with n vertices in total. This problem has numerous applications, especially in automated circuit design. In [9], deRezende, Lee and Wu present a O(n lg n) time complexity solution to the rectilinear shortest path problem when the obstacles are disjoint isothetic rectangles. In [11], Mitchell considers the case when the obstacles are rectilinear polygons and usn)2 ing a continuous Dijkstra’s approach, obtains an O( n(lg lg lg n ) algorithm. In [10] Clarkson, Kapoor, Vaidya and in [7] Mitchell study the problem where the obstacles are non-intersecting simple polygons. Two algorithms are presented in [10] : one requires O(n lg n) space and O(n(lg n)2 ) time, and the other takes O(n(lg n)3/2 ) time and O(n(lg n)3/2 ) space. The algorithm presented in [7] is of O(n lg n) time and O(n) space complexities. Typically, the number of obstacles m is much smaller than the number of vertices of all the obstacles together, n. This has been used to provide efficient algorithms for finding Euclidean shortest paths on the plane among obstacles to yield a O(n + m2 lg n) time and O(n) space algorithm by Kapoor, Maheshwari and Mitchell in [4]. In this paper, we design an algorithm for computing a rectilinear shortest path in O(n + m(lg n)3/2 ) time and O(n + m(lg m)3/2 ) space. Hershberger and Suri gave O(n lg n) time and O(n lg n) space algorithm in [2] to find an Euclidean shortest path, which uses the continuous Dijkstra approach. Since the continuous Dijkstra approach ([11] and [2]) is complicated, we use a visibility graph based approach. The visibility graph method is based V. Arvind and S. Prasad (Eds.): FSTTCS 2007, LNCS 4855, pp. 412–423, 2007. c Springer-Verlag Berlin Heidelberg 2007
Finding a Rectilinear Shortest Path in R2 Using Corridor
413
on constructing a graph whose nodes are the vertices of the obstacles and whose edges are pairs of mutually visible vertices. Welzl provides an algorithm for constructing the visibility graph with n line segments in O(n2 ) time [6]. Ghosh and Mount [3], and, Kapoor and Maheshwari [5] found an algorithm to construct the visibility graph of time complexity O(n lg n + |E|) (where |E| is the number of edges in the graph). Applying Dijkstra’s algorithm on this graph, one can determine a shortest path in O(n lg n +
Data Loading...
