Abstract
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(nlog3 n) preprocessing time, O(n log2 n) space and O(log2 n) query time for the distance problem. The actual path can be reported in O(log2 n+k where k is the number of segments in the reported path. Thus we exhibit a tradeoff between a previous result in [6] in which an exact solution of this query problem is given at the expense of O(n√n) preprocessing and O(√n+k) query time.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. J. Atallah and D. Z. Chen, Parallel rectilinear shortest paths with rectangular obstacles, Proc. 2nd Annual ACM Symposium on Parallel Algorithms and Architecture, 1990, pp. 270–279.
K. Clarkson, Approximation algorithms for shortest path motion planning, Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 56–65.
K. L. Clarkson, S. Kapoor and P. M. Vaidya, Rectilinear shortest paths through polygonal obstacles, Proc. 3rd Annual Conf. Computational Geometry, 1987, pp. 251–257.
P. J. de Rezende, D. T. Lee and Y. F. Wu, Rectilinear shortest paths in the presence of rectangular obstacles, Discrete Comput. Geom. 4, 1989, pp. 41–53.
E. W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1, 1959, pp. 269–271.
H. Elgindy and P. Mitra, Orthogonal shortest route queries among axes parallel rectangular obstacles, Int. J. of Comput. Geom. and Applications, to appear.
L. J. Guibas and J. Hershberger, Optimal shortest path queries in a simple polygon, Proc. 3rd Annual Symposium on Computational Geometry, 1987, pp. 50–63.
L. Guibas, J. Hershberger, D. Leven, M. Sharir and R. Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proc. 2nd Annual Conf. Computational Geometry, 1986, pp. 1–13.
D. G. Kirkpatrick, Optimal search in planar subdivisions, SIAM J. Comp. 12, 1983, pp. 28–35.
D. T. Lee and F. P. Preparata, Eucledian shortest paths among rectilinear barriers, Networks, 11, pp. 393–410.
J. S. B. Mitchell, L 1 shortest paths among polygonal obstacles in the plane, Algorithmica, 8(1), 1992, pp. 55–88.
J. S. B. Mitchell, Algorithmic approaches to optimal route planning, Technical Report No. 997, School of Operations Research and Industrial Engineering, Cornell University, 1990.
K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters 27, 1988, pp. 125–128.
Y. F. Wu, P. Widmayer, M. D. F. Schlag and C. K. Wong, Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles, IEEE Transactions on Computers, 36(3), 1987, pp. 321–331.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mitra, P., Bhattacharya, B. (1993). Efficient approximate shortest-path queries among isothetic rectangular obstacles. In: Dehne, F., Sack, JR., Santoro, N., Whitesides, S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57155-8_276
Download citation
DOI: https://doi.org/10.1007/3-540-57155-8_276
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57155-1
Online ISBN: 978-3-540-47918-5
eBook Packages: Springer Book Archive