Abstract
In this paper we address the following shortest-path problem. Given a point in the plane andn disjoint isothetic rectangles (barriers), we want to construct a shortestL 1 path (not crossing any of the barriers) from the source point to any given query point. A restricted version of this problem (where the source and destination points are knowna priori) had been solved earlier inO(n 2) time. Our approach consists of preprocessing the source point and the barriers to obtain a planar subdivision where a query point can be located and a shortest path connecting it to the source point quickly transvered. By showing that any such path is monotone in at least one ofx ory directions, we are able to apply a plane sweep technique to divide the plane intoO(n) rectangular regions. This leads to an algorithm whose complexity isO(n logn) preprocessing time,O(n) space, andO(logn+k) query time, wherek is the number of turns on the reported path. If only the length of the path is sought,O(logn) query time suffices. Furthermore, we show an Θ(n logn) time lower bound for the case where the source and destination points are known in advance, which implies the optimality of our algorithm in this case.
Article PDF
Similar content being viewed by others
References
V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1984.
T. Asano, L. Guibas, J. Hershberger, and H. Imai, Visibility of disjoint polygons,Algorithmica 1 (1986h), 49–63.
M. Ben-Or, Lower bounds for algebraic computation trees,Proceedings of the 15th ACM Annual Symposium on Theory of Computing, 80–86, Boston, MA, 1983.
E. W. Dijkstra, A note on two problems in connection with graphs,Numer. Math. 1 (1959), 269–271.
H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM J. Comput. 15 (1986), 317–340.
D. G. Kirkpatrick, Optimal search in planar subdivision,SIAM J. Comput. 12 (1983), 28–35.
R. C. Larson and V. O. Li, Finding minimum rectilinear distance paths in the presence of barriers,Networks 11 (1981), 285–304.
D. T. Lee, Proximity and Reachability in the Plane, Ph.D. Thesis, University of Illinois, 1978.
D. T. Lee and F. P. Preparata, Euclidean shortest paths in the presence of rectilinear barriers,Networks 14 (1984), 393–410.
T. Lozano-Perez and M. A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles,Comm. ACM 22 (1979), 560–570.
N. Sarnak and R. Tarjan, Planar point location using persistent search trees,Comm. ACM 29 (1986), 669–679.
M. I. Shamos, Computational Geometry, Ph.D. Thesis, Yale University, New Haven, CT, 1978.
M. Sharir and A. Schorr, On shortest paths in polyhedral spaces,SIAM J. Comput. 15 (1986), 193–215.
H. Vaccaro, Alternative Techniques for Modeling Travel Distance, Thesis in Civil Engineering, Massachusetts Institute of Technology, 1974.
G. E. Wangdahl, S. M. Pollack, and J. B. Woodward, Minimum-trajectory pipe routing,J. Ship Res. 18 (1974), 46–49.
E. Welzl, Constructing the visibility graph forn line segments inO(n 2) time,Inform. Process. Lett. 18 (1985), 167–171.
Author information
Authors and Affiliations
Additional information
A preliminary version of this paper appeared in theProceedings of the First Symposium on Computational Geometry (1985).
Supported in part by CNPq-Conselho Nacional de Desenvolvimento Científico e Tecnológico (Brazil).
Supported in part by the National Science Foundation under Grants MCS 8420814 and ECS 8340031.
Rights and permissions
About this article
Cite this article
de Rezende, P.J., Lee, D.T. & Wu, Y.F. Rectilinear shortest paths in the presence of rectangular barriers. Discrete Comput Geom 4, 41–53 (1989). https://doi.org/10.1007/BF02187714
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02187714