Minimum-link paths among obstacles in the plane

J.S.B. Mitchell, G. Rote, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    42 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Ea(n) log2 n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and a(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).
    Original languageEnglish
    Pages (from-to)431-459
    Number of pages29
    JournalAlgorithmica
    Volume8
    Issue number1
    DOIs
    Publication statusPublished - 1992

    Fingerprint

    Dive into the research topics of 'Minimum-link paths among obstacles in the plane'. Together they form a unique fingerprint.

    Cite this