On-line navigation in a room

E. Bar-Eli, Piotr Berman, A. Fiat, Peiyuan Yan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    20 Scopus citations


    We consider the problem of navigating through an unknown environment in which the obstacles are disjoint oriented rectangles enclosed in an n × n square room. The task of a navigating algorithm is to reach the center of the room starting from one of the corners. While there always exists a path of length n, the best previously known navigating algorithm finds paths of length n2O(√in n). We give an efficient deterministic algorithm which finds a path of length O(n In n); this algorithm uses tactile information only. Moreover, we prove that any deterministic algorithm can be forced to traverse a distance of Ω(n In n), even if it uses visual information.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
    PublisherAssociation for Computing Machinery
    Number of pages13
    ISBN (Electronic)089791466X
    StatePublished - Sep 1 1992
    Event3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992 - Orlando, United States
    Duration: Jan 27 1992Jan 29 1992

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
    VolumePart F129721


    Other3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
    Country/TerritoryUnited States

    All Science Journal Classification (ASJC) codes

    • Software
    • General Mathematics


    Dive into the research topics of 'On-line navigation in a room'. Together they form a unique fingerprint.

    Cite this