Lower bounds in on-line geometric searching metric searching

1. R. Baeza-Yates, J. Culberson, and G. Rawlins. Searching in the plane. Information and Computation, 106:234–252, 1993. 6:234-252, 1993.

   Article  Google Scholar 

2. A. Beck. On the linear search problem. Israel Journal of Math., 2: 221–228, 1964.

   Google Scholar 

3. A. Beck. More on the linear search problem. Israel Journal of Math., 3:61–70, 1965.

   Google Scholar 

4. A. Beck and D. Newman. Yet more on the linear search problem. Israel Journal of Math., 8:419–429, 1970.

   Google Scholar 

5. A. Beck and P. Warren. The return of the linear search problem. Israel Journal of Math., 10:169–183, 1972.

   Google Scholar 

6. R. Bellman. An optimal search Problem. SIAM Review, 5(2):274, 1963.

   Article  Google Scholar 

7. M. Betke, R. L. Rivest, and M. Singh. Piecemeal learning of an unknown environment. In Sixth ACM Conference on Computational Learning Theory (COLT 93), pages 277–286, July 1993.

   Google Scholar 

8. K-F. Chan and T. W. Lam. An on-line algorithm for navigating in an unknown environment. International Journal of Computational Geometry & Applications, 3:227–244, 1993.

   Google Scholar 

9. A. Datta, Ch. Hipke, and S. Schuierer. Competitive searching in polygons—beyond generalized streets. In Proc. Sixth Annual International Symposium on Algorithms and Computaion, pages 32–41. LNCS 1004, 1995.

   Google Scholar 

10. A. Datta and Ch. Icking. Competitive searching in a generalized street. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 175–182, 1994.

    Google Scholar 

11. S. Gal. A general search game. Israel Journal of Math., 12:32–45, 1972.

    Google Scholar 

12. S. Gal. Minimax solutions for linear search problems. SIAM Journal of Applied Math., 27(1):17–30, 1974.

    Article  Google Scholar 

13. S. Gal. Search Games. Academic Press, 1980.

    Google Scholar 

14. S. Gal and D. Chazan. On the optimality of the exponential functions for some minimax problems. SIAM Journal of Applied Math., 30(2):324–348, 1976.

    Article  Google Scholar 

15. Ch. Hipke. Online-Algorithmen zur kompetitiven Suche in einfachen Polygonen. Master's thesis, Universität Freiburg, 1994.

    Google Scholar 

16. M.-Y. Kao, Y. Ma, M. Sipser, and Y. Yin. Optimal constructions of hybrid algorithms. In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, pages 372–381, 1994.

    Google Scholar 

17. M.Y. Kao, J.H. Reif, and S. R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. in Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, Pages 441–447, 1993.

    Google Scholar 

18. R. Klein. Walking an unknown street with bounded detour. Comput. Geom. Theory Appl., 1:325–351, 1992.

    Google Scholar 

19. J. M. Kleinberg. On-line search in a simple polygon. In Proc. of 5th ACM-SIAM Syrnp. on Discrete Algorithms, pages 8–15, 1994.

    Google Scholar 

20. A. López-Ortiz. On-line Searching on Bounded and Unbounded Domains. PhD thesis, Department of Computer Science, University of Waterloo, 1996.

    Google Scholar 

21. A. López-Ortiz and S. Schuierer. Going home through an unknown street. In S. G. Akl, F. Dehne, and J. R. Sack, editors, Proc. 4th Workshop on Algorithms and Datastructures, pages 135–146. LNCS 955, 1995.

    Google Scholar 

22. A. López-Ortiz and S. Schuierer.Generalized streets revisited.In to appear, editor, Proc. 4th European Symposium on Algorithms, 1996.

    Google Scholar 

23. C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. In Proc. 16th Internat. Colloq. Automata Lang. Program., volume 372 of Lecture Notes in Computer Science, pages 610–620. Springer-Verlag, 1989.

    Google Scholar 

24. D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202–208, 1985.

    Article  Google Scholar 

Download references