Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Algorithms for On-Line Navigation
Authors: Kleinberg, Jon M.
Keywords: computer science
technical report
Issue Date: Nov-1992
Publisher: Cornell University
Abstract: We consider a number of problems faced by a robot trying to navigate inside a simple polygon. Such problems are "on-line"g in the sense that the robot does not have access to the map of the polygon; it must make decisions as it proceeds, based only on what it has seen so far. Specifically, we examine algorithms for the related problems of exploration and search. We present a 5/4-competitive randomized algorithm for exploring a rectilinear polygon; the only privious work here is the deterministic 2-competitive algorithm claimed in Deng, Kameda and Papadimitrou. For the problem of searching for a distinguished point in a polygon, we give a $\sqrt{3}$-competitive algorithm for traversing a street, which improves on a result of Klein by more than a factor of 3. Finally, the techniques we use in exploration and the construction of search patterns are combined to give an algorithm for searching an arbitrary and unknown rectilinear polygon; here, no constant competitive ratio can be achieved, but our algorithm is within a constant factor of optimal in the worst case.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
92-1316.pdf1.77 MBAdobe PDFView/Open
92-1316.ps195.21 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us