Journal of the ACM Bibliography
Xiaotie Deng, Tiko Kameda, and Christos Papadimitriou.
How to learn an unknown environment I: The rectilinear case.
Journal of the ACM, 45(2):215-245, March 1998.
[BibTeX entry]
Categories and Subject Descriptors:
F.2.2 [Analysis of Algorithms and Problem Complexity]:
Nonnumerical Algorithms and Problems
General Terms:
Algorithms, Theory
Additional Key Words and Phrases:
Competitive algorithms, computational geometry, gallery tour, L1 metric,
on-line algorithms, polygon with obstacles, shortest path
Selected references
- Avrim Blum, Prabhakar Raghavan, and Baruch Schieber. Navigating in
unfamiliar geometric terrain. SIAM Journal on
Computing, 26(1):110-137, January 1997.
- Wei-pang Chin and Simeon Ntafos. Optimum watchman routes.
Information Processing Letters, 28(1):39-44, 30 May 1988.
- Xiaotie Deng, Tiko Kameda, and Christos Papadimitriou. How to learn an unknown
environment (extended abstract). In 32nd Annual Symposium on
Foundations of Computer Science, pages 298-303, San Juan, Puerto
Rico, 1-4 October 1991. IEEE.
- Xiaotie Deng and Christos H. Papadimitriou. Exploring an unknown graph
(extended abstract). In 31st Annual Symposium on Foundations
of Computer Science, volume I, pages 355-361, St. Louis,
Missouri, 22-24 October 1990. IEEE.
- Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel Dominic
Sleator. Competitive
snoopy caching. Algorithmica, 3:77-119, 1988.
- Howard Karloff, Yuval Rabani, and Yiftach Ravid. Lower bounds for
randomized k-server and motion-planning algorithms.
SIAM Journal on Computing, 23(2):293-312, April 1994.
- Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list
update and paging rules. Communications of the ACM,
28(2):202-208, February 1985.
Shortcuts: