## Library Welcome Message Help

close

Attention, institutional online journal administrators: if the institution name printed in this screen message is incorrect, you can request a change by sending an email to librarynames@aip.org.

SIAM J. Comput. 33, pp. 462-486 (25 pages)

# An Optimal Competitive Strategy for Walking in Streets

Christian Icking, Rolf Klein, Elmar Langetepe, Sven Schuierer, and Ines Semrau

•   Tools
•   Share
A simple polygon P with two distinguished vertices, s and t, is called a street if the two boundary chains from s to t are mutually weakly visible. We present an on-line strategy that walks from s to t, in any unknown street, on a path at most $\sqrt{2}$ times longer than the shortest path. This matches the best lower bound previously known and settles an open problem in the area of competitive path planning. (The result was simultaneously and independently obtained by the first three authors and by the last two authors. Both papers, [C. Icking, R. Klein, and E. Langetepe, Proceedings of the 16th Symposium on Theoretical Aspects in Computer Science, Lecture Notes in Comput. Sci. 1563, Springer-Verlag, Berlin, 1999, pp. 110--120] and [S. Schuierer and I. Semrau, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, pp. 121--131], were presented at STACS'99. The present paper contains a joint full version.)

© 2004 Society for Industrial and Applied Mathematics

## KEYWORDS

68Q17, 68Q25, 68R01, 68W40

## PUBLICATION DATA

### ISSN

0097-5397 (print)
1095-7111 (online)

## ARTICLE DATA

1. Steve Alpern, Shmuel Gal, The theory of search games and rendezvous, International Series in Operations Research & Management Science, 55, Kluwer Academic Publishers, 2003xvi+319 [MathRev]
2. Ricardo Baeza-Yates, Joseph Culberson, Gregory Rawlins, Searching in the plane, Inform. and Comput., 106 (1993), 234–252 [ISI] [MathRev]
3. R. Bellman, Problem 63-9*, SIAM Rev., 5 (1963), p. 274SIREAD000005000003000274000001.
4. Piotr Berman, On-line searching and navigation, Lecture Notes in Comput. Sci., Vol. 1442, Springer, Berlin, 1998, 232–241 [MathRev]
5. Michiel Blom, Sven Krumke, Willem de Paepe, Leen Stougie, The online TSP against fair adversaries, INFORMS J. Comput., 13 (2001), 138–148
6. Avrim Blum, Prabhakar Raghavan, Baruch Schieber, Navigating in unfamiliar geometric terrain, SIAM J. Comput., 26 (1997), 110–137
7. Christoph Bröcker, Alejandro López-Ortiz, Position-independent street searching, Lecture Notes in Comput. Sci., Vol. 1663, Springer, Berlin, 1999, 241–252 [MathRev]
8. Christoph Bröcker, Sven Schuierer, Searching rectilinear streets completely, Lecture Notes in Comput. Sci., Vol. 1663, Springer, Berlin, 1999, 98–109 [MathRev]
9. S. Carlsson, B. Nilsson, Computing vision points in polygons, Algorithmica, 24 (1999), 50–75 [ISI]
10. Gautam Das, Paul Heffernan, Giri Narasimhan, LR-visibility in polygons, Comput. Geom., 7 (1997), 37–57, Fifth Canadian Conference on Computational Geometry (Waterloo, ON, 1993)
11. Pallab Dasgupta, P. Chakrabarti, S. DeSarkar, A new competitive algorithm for agent searching in unknown streets, Lecture Notes in Comput. Sci., Vol. 1180, Springer, Berlin, 1996, 147–155 [MathRev]
12. Amitava Datta, Christoph Hipke, Sven Schuierer, Competitive searching in polygons—beyond generalised streets, Lecture Notes in Comput. Sci., Vol. 1004, Springer, Berlin, 1995, 32–41 [MathRev]
13. A. Datta and C. Icking, Competitive searching in a generalized street, in Proceedings of the 10th Annual ACM Symposium on Computational Geometry, ACM Press, New York, 1994, pp. 175–182.
14. Amitava Datta, Christian Icking, Competitive searching in a generalized street, Comput. Geom., 13 (1999), 109–120
15. Amos Fiat, Gerhard Woeginger, Online algorithms, Lecture Notes in Computer Science, Vol. 1442, Springer-Verlag, 1998xviii+436, The state of the art; Papers from the Workshop on the Competitive Analysis of On-line Algorithms held in Schloss Dagstuhl, June 1996 [MathRev]
16. Shmuel Gal, Search games, Mathematics in Science and Engineering, Vol. 149, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], 1980xiv+216 [ZentralblattMath] [MathRev]
17. Subir Ghosh, Sanjeev Saluja, Optimal on-line algorithms for walking with minimum number of turns in unknown streets, Comput. Geom., 8 (1997), 241–266
18. Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel, The polygon exploration problem, SIAM J. Comput., 31 (2001), 577–600SMJCAT000031000002000577000001 [ISI] [MathRev]
19. C. Icking, Motion and Visibility in Simple Polygons, Ph.D. thesis, Department of Computer Science, FernUniversität Hagen, Germany, 1994.
20. C. Icking, R. Klein, and E. Langetepe, Searching for the Kernel of a Polygon: A Competitive Strategy Using Self-approaching Curves, Tech. Rep. 211, Department of Computer Science, FernUniversität Hagen, Germany, 1997.
21. Christian Icking, Rolf Klein, Elmar Langetepe, An optimal competitive strategy for walking in streets, Lecture Notes in Comput. Sci., Vol. 1563, Springer, Berlin, 1999, 110–120 [MathRev]
22. C. Icking, R. Klein, and L. Ma, How to look around a corner, in Proceedings of the 5th Canadian Information Processing Society Congress, University of Waterloo, Waterloo, Canada, 1993, pp. 443–448.
23. C. Icking, A. López-Ortiz, S. Schuierer, and I. Semrau, Going Home through an Unknown Street, Tech. Rep. 228, Department of Computer Science, FernUniversität Hagen, Germany, 1998.
24. Rolf Klein, Walking an unknown street with bounded detour, IEEE Comput. Soc. Press, Los Alamitos, CA, 1991, 304–313 [MathRev]
25. Rolf Klein, Walking an unknown street with bounded detour, Comput. Geom., 1 (1992), 325–351
26. Jon Kleinberg, On-line search in a simple polygon, ACM, New York, 1994, 8–15 [MathRev]
27. E. Kranakis and A. Spatharis, Almost optimal on-line search in unknown streets, in Proceedings of the 9th Canadian Conference on Computational Geometry, Kingston, ON, Canada, 1997, pp. 93–99.
28. A. López-Ortiz, On-line Target Searching in Bounded and Unbounded Domains, Ph.D. thesis, University of Waterloo, Waterloo, Canada, 1996.
29. Alejandro López-Ortiz, Sven Schuierer, Going home through an unknown street, Lecture Notes in Comput. Sci., Vol. 955, Springer, Berlin, 1995, 135–146 [MathRev]
30. Alejandro López-Ortiz, Sven Schuierer, Generalized streets revisited, Lecture Notes in Comput. Sci., Vol. 1136, Springer, Berlin, 1996, 546–558 [MathRev]
31. Alejandro López-Ortiz, Sven Schuierer, Walking streets faster, Lecture Notes in Comput. Sci., Vol. 1097, Springer, Berlin, 1996, 345–356 [MathRev]
32. A. López-Ortiz and S. Schuierer, The Exact Cost of Exploring Streets with CAB, tech. rep., Institut für Informatik, Universität Freiburg, Germany, 1998.
33. A. López-Ortiz and S. Schuierer, Lower Bounds for Searching on Generalized Streets, tech. rep., University of New Brunswick, Canada, 1998.
34. A. López-Ortiz and S. Schuierer, Online parallel heuristics and robot searching under the competitive framework, in Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Comput. Sci. 2368, Springer-Verlag, Berlin, 2002, pp. 260–269.
35. Joseph Mitchell, Geometric shortest paths and network optimization, North-Holland, Amsterdam, 2000, 633–701 [MathRev]
36. T. Ottmann, S. Schuierer, and C. A. Hipke, Kompetitive Analyse für Online-Algorithmen: Eine kommentierte Bibliographie, Tech. Rep. 61, Institut für Informatik, Universität Freiburg, Germany, 1994.
37. N. S. V. Rao, S. Kareti, W. Shi, and S. S. Iyengar, Robot Navigation in Unknown Terrains: Introductory Survey of Non-heuristic Algorithms, Tech. Rep. ORNL/TM-12410, Oak Ridge National Laboratory, Oak Ridge, TN, 1993.
38. J.-R. Sack, J. Urrutia, Handbook of computational geometry, North-Holland, 2000x+1027+I48 [MathRev]
39. Sven Schuierer, Lower bounds in on-line geometric searching, Lecture Notes in Comput. Sci., Vol. 1279, Springer, Berlin, 1997, 429–440 [MathRev]
40. Sven Schuierer, Ines Semrau, An optimal strategy for searching in unknown streets, Lecture Notes in Comput. Sci., Vol. 1563, Springer, Berlin, 1999, 121–131 [MathRev]
41. R. Seidel, personal communications via Rolf Klein, 1999.
42. I. Semrau, Analyse und experimentelle Untersuchung von Strategien zum Finden eines Ziels in Straßenpolygonen, diploma thesis, FernUniversität Hagen, Germany, 1996.
43. Daniel Sleator, Robert Tarjan, Amortized efficiency of list update and paging rules, Comm. ACM, 28 (1985), 202–208 [MathRev]
44. L. Tseng, P. Heffernan, D. Lee, Two-guard walkability of simple polygons, Internat. J. Comput. Geom. Appl., 8 (1998), 85–116