Abstract
A polygon P is a street if there exist points (u,v) on the boundary such that P is weakly visible from any path from u to v. Optimal strategies have been found for on-line searching of streets provided that the starting position of the robot is s = u and the target is located at t = v. Thus a hiding target could foil the strategy of the robot by choosing its position t in such a manner as not to realize a street. In this paper we introduce a strategy with a constant competitive ratio to search a street polygon for a target located at an arbitrary point t on the boundary, starting at any other arbitrary point s on the boundary. We also provide lower bounds for this problem. This makes streets only the second non-trivial class of polygons (after stars) known to admit a constant-competitive-ratio strategy in the general position case.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Baeza-Yates, J. Culberson and G. Rawlins. “Searching in the plane”, Information and Computation, Vol. 106, (1993), pp. 234–252.
A. Beck. “On the linear search problem”, Israel Journal of Mathematics, Vol. 2,(1964), pp. 221–228.
B. Bhattacharya and S. K. Ghosh, “Characterizing LR-visibility polygons and related problems”, Proc. 10th Canadian Conference on Comp. Geom., (1998).
C. A. Bröcker and S. Schuierer, “Searching Rectilinear Streets Completely”, In these Proceedings.
A. Datta, Ch. Hipke, and S. Schuierer. “Competitive searching in polygons-beyond generalized streets”, in Proc. 6th Int. Symposium on Algorithms and Computation (ISAAC), pages 32–41. LNCS 1004, 1995.
A. Datta and Ch. Icking. “Competitive searching in a generalized street”, Proceedings 10th ACM Symposium on Computational Geometry (SoCG), (1994), pp. 175–182.
S. Gal. Search Games, Academic Press, 1980.
Ch. Icking. “Motion and visibility in simple polygons.” Ph.D. Thesis, Fernuniversität Hagen, 1994.
Ch. Icking and R. Klein. “Searching for the kernel of a polygon. A competitive Strategy”, Proc. 11th ACM Symposium on Computational Geometry (SoCG), (1995).
Ch. Icking, R. Klein and E. Langetepe. “An Optimal Competitive Strategy for Walking in Streets.” Tech.Rep. 233, Dept. of Comp. Sci., FernUniversität Hagen, Germany, 1998.
B. Kalyasundaram and K. Pruhs. “A competitive analysis of algorithms for searching unknown scenes”, Comp. Geom.: Theory and Applications, Vol. 3, (1993), pp. 139–155.
M.-Y. Kao, J. H. Reif and S. R. Tate. “Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem”, Proceedings of 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), (1993), pp. 441–447.
R. Klein. “Walking an unknown street with bounded detour”, Comp. Geom.: Theory and Applications, Vol. 1, (1992), pp. 325–351, also in 32nd FOCS, 1991.
J. Kleinberg. “On-line search in a simple polygon”, Proceedings of 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), (1994), pp. 8–15.
A. López-Ortiz. “On-line target searching in bounded and unbounded domains”, Ph.D. thesis, University of Waterloo, 1996.
A. López-Ortiz and S. Schuierer. “Going home through an unknown street”, Proc. 4th Workshop on Data Structures and Algorithms (WADS), 1995, Lecture Notes in Computer Science 955, Springer-Verlag, pp. 135–146.
A. López-Ortiz and S. Schuierer. “Generalized streets revisited”, In J. Diaz and M. Serna, editors, Proc. 4th European Symposium on Algorithms (ESA), LNCS 1136, pages 546–558. Springer Verlag, 1996.
A. López-Ortiz and S. Schuierer. “Walking streets faster”, Proc. 5th Scandina-vian Workshop in Algorithmic Theory Algorithms (SWAT), 1996, Lecture Notes in Computer Science 1097, Springer-Verlag, pp. 345–356.
A. López-Ortiz and S. Schuierer. “Position-independent Near Optimal Searching and On-line Recognition in Star Polygons”, Proc. 5th Workshop on Algorithms and Data Structures (WADS), (1997), Lecture Notes in Computer Science, pp. 284–296.
S. Schuierer and I. Semrau. “An optimal strategy for searching in unknown streets.” Proc. 16th Symp. on Theoretical Aspects of Computer Science, to appear, 1999
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bröcker, C.A., López-Ortiz, A. (1999). Position-Independent Street Searching. In: Dehne, F., Sack, JR., Gupta, A., Tamassia, R. (eds) Algorithms and Data Structures. WADS 1999. Lecture Notes in Computer Science, vol 1663. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48447-7_25
Download citation
DOI: https://doi.org/10.1007/3-540-48447-7_25
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66279-2
Online ISBN: 978-3-540-48447-9
eBook Packages: Springer Book Archive