{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:12Z","timestamp":1742596812967,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575689"},{"type":"electronic","value":"9783540482338"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57568-5_266","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:09:59Z","timestamp":1330261799000},"page":"353-362","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Robot mapping: Foot-prints vs tokens"],"prefix":"10.1007","author":[{"given":"Xiaotie","family":"Deng","sequence":"first","affiliation":[]},{"given":"Andy","family":"Mirzaian","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"38_CR1","unstructured":"E. Bar-Eli, P. Berman, A. Fiat, and P. Yan, \u201cOnline Navigation in a Room,\u201d SODA 1992, pp. 237\u2013249."},{"key":"38_CR2","unstructured":"R.A. Baeza-Yates, J.C. Culberson, and G.J.E. Rawlins, \u201cSearching in the Plane,\u201d To appear in Information and Computation."},{"key":"38_CR3","first-page":"335","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"K.S.Booth, G.S.Lueker [1976] \u201cTesting the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms\u201d J.CSS. 13 (1976), 335\u2013379.","journal-title":"J.CSS."},{"key":"38_CR4","volume-title":"Extremal Graph Theory","author":"B. Bollobas","year":"1978","unstructured":"B. Bollobas, \u201cExtremal Graph Theory,\u201d Academic Press, San Francisco, 1978."},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Raghavan and B. Schieber, \u201cNavigating in Unfamiliar Geometric Terrain,\u201d STOC 1991, pp.494\u2013504.","DOI":"10.1145\/103418.103419"},{"key":"38_CR6","first-page":"54","volume":"30","author":"N. Chiba","year":"1985","unstructured":"N.Chiba, T.Nishizeki, S.Abe [1985] \u201cA linear algorithm for embedding planar graphs using PQ-trees\u201d J.CSS. 30 (1985), 54\u201376.","journal-title":"J.CSS."},{"key":"38_CR7","unstructured":"G.Dudek, M. Jenkin, E. Milios, D. Wilkes, \u201cUsing Multiple markers in graph exploration,\u201d SPIE Vol. 1195 Mobile Robots IV(1989), pp.77\u201387."},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"X. Deng, T. Kameda and C. H. Papadimitriou, \u201cHow to Learn an Unknown Environment,\u201d FOCS 1991, pp.298\u2013303.","DOI":"10.1109\/SFCS.1991.185382"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"X. Deng, and C. H. Papadimitriou, \u201cExploring an Unknown Graph,\u201d FOCS 1990, pp.355\u2013361.","DOI":"10.1109\/FSCS.1990.89554"},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"A. Fiat, D.P. Foster, H. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan, \u201cCompetitive Algorithms for Layered Graph Traversal,\u201d FOCS 1991, pp.288\u2013297.","DOI":"10.1109\/SFCS.1991.185381"},{"key":"38_CR11","unstructured":"L.J. Guibas and R. Motwani and P. Raghavan, \u201c The Robot Localization Problem in Two Dimensions\u201d, SODA 1992, pp. 259\u2013268."},{"issue":"4","key":"38_CR12","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J.E. Hopcroft","year":"1973","unstructured":"J.E.Hopcroft, R.E.Tarjan [1973] \u201cEfficient planarity testing\u201d, JACM 21(4), 1973, 549\u2013568.","journal-title":"JACM"},{"key":"38_CR13","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0921-8890(91)90014-C","volume":"8","author":"B. Kuipers","year":"1991","unstructured":"B. Kuipers, and Y. Byun, \u201cA Robot Exploration and Mapping Strategy Based on a Semantic Hierarchy of Spatial Representatinos,\u201d Robotics and Autonomous Systems 8 (1991) 47\u201363.","journal-title":"Robotics and Autonomous Systems"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"R. Klein, \u201cWalking an Unknown Street with Bounded Detour,\u201d FOCS 1991, pp. 304\u2013313.","DOI":"10.1109\/SFCS.1991.185383"},{"key":"38_CR15","unstructured":"B. Kalyanasundaram, and K. Pruhs, \u201cA Competitive Analysis of Algorithms for Search Unknown Scenes,\u201d manuscripts, 1991."},{"key":"38_CR16","doi-asserted-by":"crossref","unstructured":"H. Karloff, Y. Rabani, and Y. Ravid, \u201cLower Bounds for Randomized k-Server and Motion-Planning Algorithms,\u201d STOC 1991, pp. 278\u2013288.","DOI":"10.1145\/103418.103450"},{"key":"38_CR17","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0004-3702(90)90027-W","volume":"44","author":"T.S. Levitt","year":"1990","unstructured":"T.S. Levitt, and D. T. Lawton, \u201cQualitative Navigation for Mobile Robots,\u201d Artificial Intelligence 44 (1990), 305\u2013360.","journal-title":"Artificial Intelligence"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis, \u201cShortest paths without a map,\u201d Proc. 16th ICALP, 1989, pp.610\u2013620.","DOI":"10.1007\/BFb0035787"},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"R. L. Rivest and R. E. Schapire, \u201cInference of Finite Automata Using Homing Sequences,\u201d STOC 1989, pp.411\u2013420.","DOI":"10.1145\/73007.73047"},{"issue":"2","key":"38_CR20","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D. and Tarjan, R.E., Amortized efficiency of list update and paging rules,\u201d Communications of the ACM 28(2), 1985, pp. 202\u2013208.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57568-5_266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:11:48Z","timestamp":1742595108000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57568-5_266"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575689","9783540482338"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-57568-5_266","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}