Online navigation in a room

Eldad Bar-Eli, Piotr Berman, Amos Fiat, Peiyuan Yan

    Research output: Contribution to journalArticlepeer-review

    39 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(√logn). We give an efficient deterministic algorithm which finds a path of length O(n log n); this algorithm uses tactile information only. Moreover, we prove that any deterministic algorithm can be forced to traverse a distance of Ω(n log n), even if it uses visual information.

    Original languageEnglish (US)
    Pages (from-to)319-341
    Number of pages23
    JournalJournal of Algorithms
    Issue number3
    StatePublished - Nov 1994

    All Science Journal Classification (ASJC) codes

    • Control and Optimization
    • Computational Mathematics
    • Computational Theory and Mathematics


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

    Cite this