{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:51Z","timestamp":1787337471277,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We consider the problem of localizing a robot in a known environment modeled by a simple polygon P. We assume that the robot has a map of P but is placed at an unknown location inside P. From its initial location, the robot sees a set of points called the visibility polygon V of its location. In general, sensing at a single point will not suffice to uniquely localize the robot, since the set H of points in P with visibility polygon V may have more than one element. Hence, the robot must move around and use range sensing and a compass to determine its position (i.e., localize itself). We seek a strategy that minimizes the distance the robot travels to determine its exact location.<\/jats:p>\n                  <jats:p>We show that the problem of localizing a robot with minimum travel is NP-hard. We then give a polynomial time approximation scheme that causes the robot to travel a distance of at most (k - 1)d, where k = |H|, which is no greater than the number of reflex vertices of P, and d is the length of a minimum length tour that would allow the robot to verify its true initial location by sensing. We also show that this bound is the best possible.<\/jats:p>","DOI":"10.1137\/s0097539794279201","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"583-604","source":"Crossref","is-referenced-by-count":41,"title":["Localizing a Robot with Minimum Travel"],"prefix":"10.1137","volume":"27","author":[{"given":"Gregory","family":"Dudek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kathleen","family":"Romanik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sue","family":"Whitesides","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"E. M. Arkin, H. Meijer, J. S. Mitchell, D. Rappaport, and S. S. Skiena,\n                      Decision trees for geometric models\n                      , in Proceedings of the Ninth Annual Symposium on Computational Geometry, San Diego, CA, May 19\u201021 1993, ACM Press, pp. 369\u2013378.","DOI":"10.1145\/160985.161167"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80066-1"},{"key":"R3","unstructured":"E. Bar\u2010Eli, P. Berman, A. Fiat, and P. Yan,\n                      On\u2010line navigation in a room\n                      , in Proceedings of the Third Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Orlando, FL, January 27\u201329 1992, pp. 237\u2013249."},{"key":"R4","unstructured":"R. Basri and E. Rivlin,\n                      Homing using combinations of model views\n                      , in Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI\u201093), Chambery, France, August 1993, Morgan Kaufman Publishers, pp. 1586\u20131591."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"K. Basye and T. Dean,\n                      Map learning with indistinguishable locations\n                      , in Uncertainty in Artificial Intelligence 5, M. Henrion and L. N. Kanal and J. F. Lemmer, eds., Elsevier Science Publishers, 1990, pp. 331\u2013340.","DOI":"10.1016\/B978-0-444-88738-2.50033-6"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90022-X"},{"key":"R7","unstructured":"P. Berman, A. Blum, A. Fiat, H. Karloff, A. Rosen, and M. Saks,\n                      Randomized robot navigation algorithms\n                      , in Proceedings of the Seventh Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Atlanta, GA, January 28\u201330 1996, pp. 75\u201384."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Betke and L. Gurvits,\n                      Mobile robot localization using landmarks\n                      , in Proceedings of the IEEE\/RSJ\/GI International Conference on Intelligent Robots and Systems, Munich, Germany, September 1994, pp. 135\u2013142. To appear in\n                      IEEE Trans. on Robotics and Automation\n                      .","DOI":"10.1109\/IROS.1994.407399"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194931"},{"key":"R10","unstructured":"P. K. Bose,\n                      Visibility in Simple Polygons\n                      , master\u2019s thesis, University of Waterloo, Waterloo, Ontario, Canada, December 1991."},{"key":"R11","unstructured":"P. K. Bose, A. Lubiw, and J. I. Munro,\n                      Efficient visibility queries in simple polygons\n                      , in Proceedings of the Fourth Canadian Conference on Computational Geometry, C. A. Wang, ed., St. John\u2019s, Newfoundland, Canada, August 10\u201014 1992, Memorial University of Newfoundland, pp. 23\u201328."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"A. Datta and C. Icking,\n                      Competitive searching in a generalized street\n                      , in Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, NY, June 6\u20138 1994, ACM Press, pp. 175\u2013182.","DOI":"10.1145\/177424.177622"},{"key":"R13","unstructured":"E. Davis,\n                      Representing and Acquiring Geographic Knowledge\n                      , Pitman and Morgan Kaufmann Publishers, Inc., London and Los Altos, CA, 1986."},{"key":"R14","unstructured":"G. Dudek, M. Jenkin, E. Milios, and D. Wilkes,\n                      Map validation and self\u2010location in a graph\u2010like world\n                      , in Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI\u201093), Chambery, France, August 1993, Morgan Kaufman Publishers, pp. 1648\u20131653."},{"key":"R15","first-page":"21","volume":"25","author":"Eades P.","year":"1993","journal-title":"Austral. Computing J.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-8917","issn-type":"print"},{"key":"R16","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90019-5"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"R19","unstructured":"Leonidas Guibas, Rajeev Motwani, Prabhakar Raghavan, The robot localization problem in two dimensions, ACM, New York, 1992, 259\u201326894c:68200"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90095-8"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90010-P"},{"key":"R22","unstructured":"J. Kleinberg,\n                      On\u2010line search in a simple polygon\n                      , in Proceedings of the Fifth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, 1994, pp. 8\u201315."},{"key":"R23","unstructured":"The localization problem for mobile robots\n                      , in Proceedings of the 35th Annual Foundations of Computer Science, Santa Fe, NM, November 20\u201322 1994, IEEE Computer Society Press, pp. 521\u2013533."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"A. Kosaka, M. Meng, and A. C. Kak,\n                      Vision\u2010guided mobile robot navigation using retroactive updating of position uncertainty\n                      , in Proceedings of the International Conference of Robotics and Automation, Volume 2, Atlanta, GA, May 1993, IEEE Computer Society Press, pp. 1\u20137.","DOI":"10.1109\/ROBOT.1993.292115"},{"key":"R25","unstructured":"B. J. Kuipers and Y. T. Byun,\n                      A qualitative approach to robot exploration and map\u2010learning\n                      , in Proceedings of the IEEE Workshop on Spatial Reasoning and Multi\u2010Sensor Fusion, Los Altos, CA, 1987, IEEE, pp. 390\u2013404."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"J.\u2010C. Latombe,\n                      Robot Motion Planning\n                      , Kluwer Academic Publishers, Norwell, MA, 1991.","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140304"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90263-2"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/70.163782"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794279201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:19Z","timestamp":1787335939000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794279201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794279201"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794279201","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}