ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
Hossam A. ElGindy, Pinaki Mitra · International Journal of Computational Geometry & Applications · 1994
Given a set ℬ of n barriers, the shortest route query SRQ problem asks for a preprocessing of ℬ such that a description of the shortest route between two points (origin and destination) can be reported efficiently. In this manuscript we present efficient sequential and parallel algorithms for the SRQ problem where the barriers in ℬ are disjoint planar rectangles whose sides are parallel to the coordinate axes, and subsequent queries ask for the shortest L 1 route between two arbitrary points which avoids the barriers in ℬ. The segments forming such route are also restricted to be parallel to the coordinate axes. For this problem we we present sequential and parallel preprocessing algorithms which allow for reporting the shortest distance between two arbitrary query points in O( log n) time with a single processor. The route itself can also be constructed in time proportional to its number of segments. Our method is based on constructing three planar graphs, called carrier graphs, that contain the shortest route information in a succinct form. Each graph can then be searched using graph theoretic techniques. Using the same techniques we also present a parallel algorithm for computing the orthogonal shortest distance between two points among rectangular obstacles which runs in poly-logarithmic time using sub-quadratic number of processors on the CREW PRAM model of computation.