Summary: In this paper we consider the problem of approximate rectilinear shortest-path query between two arbitrary points in the presence of \(n\) isothetic and disjoint rectangular obstacles. We present an algorithm which reports a path whose length is at most three times the optimal path length between two arbitrary corner points and at most seven times the optimal path length between two arbitrary points. Our algorithm takes \(O(n \log^3n)\) preprocessing time, \( O(n \log^2 n)\) space and \(O(\log^2 n)\) query time for the distance problem. The actual path can be reported in \(O(\log^2 n+k\) where \(k\) is the number of segments in the reported path. Thus we exhibit a tradeoff between a previous result in [H. Elgindy and P. Mitra, Int. J. Comput. Geom. Appl. 4, No. 1, 3–24 (1994; Zbl 0805.68126)] in which an exact solution of this query problem is given at the expense of \(O(n\sqrt{n})\) preprocessing and \(O( \sqrt{n}+k)\) query time.
For the entire collection see [Zbl 0825.00122].