{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:16:17Z","timestamp":1760440577726},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540433996"},{"type":"electronic","value":"9783540459934"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45993-6_14","type":"book-chapter","created":{"date-parts":[[2007,7,20]],"date-time":"2007-07-20T20:10:22Z","timestamp":1184962222000},"page":"245-258","source":"Crossref","is-referenced-by-count":23,"title":["On the Competitive Complexity of Navigation Tasks"],"prefix":"10.1007","author":[{"given":"Christian","family":"Icking","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Kamphans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elmar","family":"Langetepe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,4,23]]},"reference":[{"key":"14_CR1","unstructured":"S. Albers, K. Kursawe, and S. Schuierer. Exploring unknown environments with obstacles. In Proc. 10th ACM-SIAM Sympos. Discrete Algorithms, pages 842\u2013843, 1999."},{"key":"14_CR2","unstructured":"E. M. Arkin, S. P. Fekete, and J. S. B. Mitchell. Approximation algorithms for lawn mowing and milling. Technical report, Mathematisches Institut, Universit\u00e4t zu K\u00f6ln, 1997."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proc. 37th Annu. IEEE Sympos. Found. Comput. Sci., pages 2\u201311, 1996.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R. Baeza-Yates","year":"1993","unstructured":"R. Baeza-Yates, J. Culberson, and G. Rawlins. Searching in the plane. Inform. Comput., 106:234\u2013252, 1993.","journal-title":"Inform. Comput."},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"R. Bellman. Problem 63-9*. SIAM Review, 5(2), 1963.","DOI":"10.1137\/1005046"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"C. Br\u00f6cker and A. L\u00f3pez-Ortiz. Position-independent street searching. In Proc. 6th Workshop Algorithms Data Struct., volume 1663 of Lecture Notes Comput. Sci., pages 241\u2013252. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-48447-7_25"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"C. Br\u00f6cker and S. Schuierer. Searching rectilinear streets completely. In Proc. 6th Workshop Algorithms Data Struct., volume 1663 of Lecture Notes Comput. Sci., pages 98\u2013109. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-48447-7_12"},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/PL00009271","volume":"24","author":"S. Carlsson","year":"1999","unstructured":"S. Carlsson and B. J. Nilsson. Computing vision points in polygons. Algorithmica, 24:50\u201375, 1999.","journal-title":"Algorithmica"},{"key":"14_CR9","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0925-7721(95)00042-9","volume":"7","author":"G. Das","year":"1997","unstructured":"G. Das, P. Heffernan, and G. Narasimhan. LR-visibility in polygons. Comput. Geom. Theory Appl., 7:37\u201357, 1997.","journal-title":"Comput. Geom. Theory Appl."},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"P. Dasgupta, P. P. Chakrabarti, and S. C. DeSarkar. A new competitive algorithm for agent searching in unknown streets. In Proc. 16th Conf. Found. Softw. Tech. Theoret. Comput. Sci., volume 1180 of Lecture Notes Comput. Sci., pages 147\u2013155. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-62034-6_45"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"A. Datta, C. A. Hipke, and S. Schuierer. Competitive searching in polygons: Beyond generalised streets. In Proc. 6th Annu. Internat. Sympos. Algorithms Comput., volume 1004 of Lecture Notes Comput. Sci., pages 32\u201341. Springer-Verlag, 1995.","DOI":"10.1007\/BFb0015406"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"A. Datta and C. Icking. Competitive searching in a generalized street. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 175\u2013182, 1994.","DOI":"10.1145\/177424.177622"},{"key":"14_CR13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0925-7721(99)00015-2","volume":"13","author":"A. Datta","year":"1999","unstructured":"A. Datta and C. Icking. Competitive searching in a generalized street. Comput. Geom. Theory Appl., 13:109\u2013120, 1999.","journal-title":"Comput. Geom. Theory Appl."},{"key":"14_CR14","series-title":"Report","volume-title":"Hamiltonian paths in non-rectangular grid graphs","author":"H. Everett","year":"1986","unstructured":"H. Everett. Hamiltonian paths in non-rectangular grid graphs. Report 86-1, Dept. Comput. Sci., Univ. Toronto, Toronto, ON, 1986."},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"A. Fiat and G. Woeginger, editors. On-line Algorithms: The State of the Art, volume 1442 of Lecture Notes Comput. Sci. Springer-Verlag, 1998.","DOI":"10.1007\/BFb0029561"},{"key":"14_CR16","volume-title":"Mathematics in Science and Engeneering","author":"S. Gal","year":"1980","unstructured":"S. Gal. Search Games, volume 149 of Mathematics in Science and Engeneering. Academic Press, New York, 1980."},{"issue":"5","key":"14_CR17","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0925-7721(97)00003-5","volume":"8","author":"S. K. Ghosh","year":"1997","unstructured":"S. K. Ghosh and S. Saluja. Optimal on-line algorithms for walking with minimum number of turns in unknown streets. Comput. Geom. Theory Appl., 8(5):241\u2013266, Oct. 1997.","journal-title":"Comput. Geom. Theory Appl."},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"M. Grigni, E. Koutsoupias, and C. H. Papadimitriou. An approximation scheme for planar graph TSP. In Proc. 36th Annu. IEEE Sympos. Found. Comput. Sci., pages 640\u2013645, 1995.","DOI":"10.1109\/SFCS.1995.492665"},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(99)00009-8","volume":"93","author":"C. Hipke","year":"1999","unstructured":"C. Hipke, C. Icking, R. Klein, and E. Langetepe. How to find a point on a line within a fixed distance. Discrete Appl. Math., 93:67\u201373, 1999.","journal-title":"Discrete Appl. Math."},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"F. Hoffmann, C. Icking, R. Klein, and K. Kriegel. The polygon exploration problem. SIAM J. Comput., 2001. to appear.","DOI":"10.1137\/S0097539799348670"},{"key":"14_CR21","unstructured":"C. Icking. Motion and Visibility in Simple Polygons. PhD thesis, Department of Computer Science, FernUniversit\u00e4t Hagen, 1994."},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"C. Icking, R. Klein, and E. Langetepe. An optimal competitive strategy for walking in streets. In Proc. 16th Sympos. Theoret. Aspects Comput. Sci., volume 1563 of Lecture Notes Comput. Sci., pages 110\u2013120. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-49116-3_10"},{"key":"14_CR23","unstructured":"C. Icking, R. Klein, and E. Langetepe. Searching a goal on m rays within a fixed distance. In Abstracts 15th European Workshop Comput. Geom., pages 137\u2013139. INRIA Sophia-Antipolis, 1999."},{"key":"14_CR24","series-title":"Technical Report","volume-title":"Going home through an unknown street","author":"C. Icking","year":"1998","unstructured":"C. Icking, A. L\u00f3pez-Ortiz, S. Schuierer, and I. Semrau. Going home through an unknown street. Technical Report 228, Department of Computer Science, FernUniversit\u00e4t Hagen, Germany, 1998."},{"key":"14_CR25","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter. Hamilton paths in grid graphs. SIAM J. Comput., 11:676\u2013686, 1982.","journal-title":"SIAM J. Comput."},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"R. Klein. Walking an unknown street with bounded detour. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 304\u2013313, 1991.","DOI":"10.1109\/SFCS.1991.185383"},{"key":"14_CR27","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0925-7721(92)90010-P","volume":"1","author":"R. Klein","year":"1992","unstructured":"R. Klein. Walking an unknown street with bounded detour. Comput. Geom. Theory Appl., 1:325\u2013351, 1992.","journal-title":"Comput. Geom. Theory Appl."},{"key":"14_CR28","unstructured":"J. M. Kleinberg. On-line search in a simple polygon. In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, pages 8\u201315, 1994."},{"key":"14_CR29","unstructured":"E. Kranakis and A. Spatharis. Almost optimal on-line search in unknown streets. In Proc. 9th Canad. Conf. Comput. Geom., pages 93\u201399, 1997."},{"key":"14_CR30","unstructured":"E. Langetepe. Design and Analysis of Strategies for Autonomous Systems in Motion Planning. PhD thesis, Department of Computer Science, FernUniversit\u00e4t Hagen, 2000."},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"A. L\u00f3pez-Ortiz and S. Schuierer. Going home through an unknown street. In Proc. 4th Workshop Algorithms Data Struct., volume 955 of Lecture Notes Comput. Sci., pages 135\u2013146. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60220-8_57"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"A. L\u00f3pez-Ortiz and S. Schuierer. Generalized streets revisited. In Proc. 4th Annu. European Sympos. Algorithms, volume 1136 of Lecture Notes Comput. Sci., pages 546\u2013558. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-61680-2_81"},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"A. L\u00f3pez-Ortiz and S. Schuierer. Walking streets faster. In Proc. 5th Scand. Workshop Algorithm Theory, volume 1097 of Lecture Notes Comput. Sci., pages 345\u2013356. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-61422-2_144"},{"key":"14_CR34","unstructured":"A. L\u00f3pez-Ortiz and S. Schuierer. The exact cost of exploring streets with CAB. Technical report, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, 1998."},{"key":"14_CR35","volume-title":"Lower bounds for searching on generalized streets","author":"A. L\u00f3pez-Ortiz","year":"1998","unstructured":"A. L\u00f3pez-Ortiz and S. Schuierer. Lower bounds for searching on generalized streets. University of New Brunswick, Canada, 1998."},{"key":"14_CR36","unstructured":"J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple new method for the geometric k-MST problem. In Proc. 7th ACM-SIAM Sympos. Discrete Algorithms, pages 402\u2013408, 1996."},{"key":"14_CR37","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/B978-044482537-7\/50016-4","volume-title":"Handbook of Computational Geometry","author":"J. S. B. Mitchell","year":"2000","unstructured":"J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633\u2013701. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000."},{"issue":"3","key":"14_CR38","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0925-7721(92)90014-J","volume":"1","author":"S. Ntafos","year":"1992","unstructured":"S. Ntafos. Watchman routes under limited visibility. Comput. Geom. Theory Appl., 1(3):149\u2013170, 1992.","journal-title":"Comput. Geom. Theory Appl."},{"key":"14_CR39","doi-asserted-by":"crossref","unstructured":"S. Schuierer. Lower bounds in on-line geometric searching. In 11th International Symposium on Fundamentals of Computation Theory, volume 1279 of Lecture Notes Comput. Sci., pages 429\u2013440. Springer-Verlag, 1997.","DOI":"10.1007\/BFb0036204"},{"key":"14_CR40","doi-asserted-by":"crossref","unstructured":"S. Schuierer and I. Semrau. An optimal strategy for searching in unknown streets. In Proc. 16th Sympos. Theoret. Aspects Comput. Sci., volume 1563 of Lecture Notes Comput. Sci., pages 121\u2013131. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-49116-3_11"},{"key":"14_CR41","unstructured":"I. Semrau. Analyse und experimentelle Untersuchung von Strategien zum Finden eines Ziels in Stra\u03b2enpolygonen. Diploma thesis, FernUniversit\u00e4t Hagen, 1996."},{"key":"14_CR42","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28:202\u2013208, 1985.","journal-title":"Commun. ACM"},{"issue":"1","key":"14_CR43","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1142\/S0218195998000060","volume":"8","author":"L. H. Tseng","year":"1998","unstructured":"L. H. Tseng, P. Heffernan, and D. T. Lee. Two-guard walkability of simple polygons. Internat. J. Comput. Geom. Appl., 8(1):85\u2013116, 1998.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"14_CR44","doi-asserted-by":"crossref","unstructured":"C. Umans and W. Lenhart. Hamiltonian cycles in solid grid graphs. In Proc. 38th Annu. IEEE Sympos. Found. Comput. Sci., pages 496\u2013507, 1997.","DOI":"10.1109\/SFCS.1997.646138"}],"container-title":["Lecture Notes in Computer Science","Sensor Based Intelligent Robots"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45993-6_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T11:06:58Z","timestamp":1556708818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45993-6_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540433996","9783540459934"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/3-540-45993-6_14","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}