{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T19:03:25Z","timestamp":1791140605115,"version":"4.1.0"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1997,2]]},"abstract":"<jats:p>Consider a robot that has to travel from a start location s to a target t in an environment with opaque obstacles that lie in its way. The robot always knows its current absolute position and that of the target. It does not, however, know the positions and extents of the obstacles in advance; rather, it finds out about obstacles as it encounters them. We compare the distance walked by the robot in going from s to t to the length of the shortest (obstacle-free) path between s and t in the scene. We describe and analyze robot strategies that minimize this ratio for different kinds of scenes. In particular, we consider the cases of rectangular obstacles aligned with the axes, rectangular obstacles in more general orientations, and wider classes of convex bodies both in two and three dimensions. For many of these situations, our algorithms are optimal up to constant factors. We study scenes with nonconvex obstacles, which are related to the study of maze traversal. We also show scenes where randomized algorithms are provably better than deterministic algorithms.<\/jats:p>","DOI":"10.1137\/s0097539791194931","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"110-137","source":"Crossref","is-referenced-by-count":75,"title":["Navigating in Unfamiliar Geometric Terrain"],"prefix":"10.1137","volume":"26","author":[{"given":"Avrim","family":"Blum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prabhakar","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1054"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1039"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"S. Ben\u2010David, A. Borodin, R. M. Karp, G. Tardos, and A. Wigderson,\n                      On the power of randomization in on\u2010line algorithms\n                      , in Proc. 22nd Annual ACM Symposium on Theory of Computing, ACM, New York, 1990, pp. 379\u2013388.","DOI":"10.1145\/100216.100268"},{"key":"R4","unstructured":"A. Blum, A. Borodin, D. Foster, H. J. Karloff, Y. Mansour, P. Raghavan, M. Saks, and B. Schieber,\n                      Randomized on\u2010line algorithms for graph closures\n                      , unpublished manuscript, 1990."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Manuel Blum, Dexter Kozen, On the power of the compass (or, why mazes are easier to search than graphs), IEEE, Long Beach, Calif., 1978, 0\u20130, 132\u2013142,80f:68064","DOI":"10.1109\/SFCS.1978.30"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Borodin, N. Linial, and M. Saks,\n                      An optimal online algorithm for metrical task systems\n                      , in Proc. 19th Annual ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 373\u2013382.","DOI":"10.1145\/28395.28435"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1177\/027836498900800503"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari,\n                      The electrical resistance of a graph captures its commute and cover times\n                      , in Proc. 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 574\u2013586.","DOI":"10.1145\/73007.73062"},{"key":"R9","first-page":"752","volume":"1095","author":"Cheng L.","year":"1989","journal-title":"Proc. Internat. Soc. Opt. Engrg."},{"key":"R10","unstructured":"M. Chrobak, H. J. Karloff, T. Payne, and S. Vishwanathan,\n                      New results on server problems\n                      , in Proc. 1st ACM\u2013SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1990, pp. 291\u2013300."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson,\n                      Approximation algorithms for shortest path motion planning\n                      , in Proc. 19th ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 56\u201365.","DOI":"10.1145\/28395.28402"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220404"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Daily, J. Harris, D. Keirsey, D. Olin, D. Payton, K. Reiser, J. Rosenblatt, D. Tseng, and V. Wong,\n                      Autonomous cross\u2010country navigation with the ALV\n                      , in Proc. IEEE International Conference on Robotics and Automation, Vol. 2, IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 718\u2013726.","DOI":"10.1109\/ROBOT.1988.12144"},{"key":"R14","first-page":"21","volume":"25","author":"Eades P.","year":"1993","journal-title":"Austral. Comput. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-8917","issn-type":"print"},{"key":"R15","unstructured":"J. Hallam, P. Forster, and J. Howe,\n                      Map free localization in a partially moving 3\u2010D world: The Edinburgh feature based navigator\n                      , in Proc. International Conference on Intelligent Autonomous Systems, Vol. 2, IOS Press, Burke, VA, 1989, pp. 726\u2013736."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90032-2"},{"key":"R17","unstructured":"H. J. Karloff, Y. Rabani, and Y. Ravid,\n                      Lower bounds for randomized server algorithms\n                      , in Proc. 23rd ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 278\u2013288."},{"key":"R18","unstructured":"R. Klein,\n                      Walking an unknown street with bounded detour\n                      , in Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1991, pp. 303\u2013313."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"V. Lumelsky,\n                      Algorithmic issues of sensor\u2010based robot motion planning\n                      , in Proc. 26th IEEE Conference on Decision and Control, IEEE Computer Society Press, Los Alamitos, CA, 1987, pp. 1796\u20131801.","DOI":"10.1109\/CDC.1987.272799"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(87)90025-2"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1986.1104175"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90140-6"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1983.12684"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1987.1087133"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Christos Papadimitriou, Mihalis Yannakakis, Shortest paths without a map (extended abstract), Lecture Notes in Comput. Sci., Vol. 372, Springer, Berlin, 1989, 610\u20136201037079","DOI":"10.1007\/BFb0035787"},{"key":"R27","first-page":"37","volume":"22","author":"Rao N. S. V.","year":"1989","journal-title":"IEEE Trans. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9340","issn-type":"print"},{"key":"R28","unstructured":"N. S. V. Rao, S. S. Iyengar, and G. deSaussure,\n                      The visit problem: visibility graph based solution\n                      , in Proc. IEEE International Conference on Robotics and Automation, IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 1650\u20131655."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/56.812"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"C. N. Shen and G. Nagy,\n                      Autonomous navigation to provide long distance surface traverses for Mars rover sample return mission\n                      , in Proc. IEEE International Symposium on Intelligent Control, IEEE Computer Society Press, Los Alamitos, CA, 1989, pp. 362\u2013367.","DOI":"10.1109\/ISIC.1989.238673"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R32","unstructured":"C.\u2010K. Yap,\n                      Algorithmic motion planning\n                      , in Advances in Robotics, J. T. Schwartz and C. K. Yap, eds., Lawrence Erlbaum Associates, Hillsdale, NJ, 1987, pp. 95\u2013144."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539791194931","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:43Z","timestamp":1787336023000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539791194931"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,2]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,2]]}},"alternative-id":["10.1137\/S0097539791194931"],"URL":"https:\/\/doi.org\/10.1137\/s0097539791194931","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,2]]}}}