On parallel rectilinear obstacle- avoiding paths

AbstractWe give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n2/log n) CREW PRAM processors, as opposed to the previous O(n2), and with O(n2) space, as opposed to the previous O(n2(log n)2). The time complexity remains unchanged, at O((log n)2). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(⌈k/log n⌉) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well