Minimum-link paths among obstacles in the plane

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    50 Citaten (Scopus)
    1 Downloads (Pure)


    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).
    Originele taal-2Engels
    Pagina's (van-tot)431-459
    Aantal pagina's29
    Nummer van het tijdschrift1
    StatusGepubliceerd - 1992


    Duik in de onderzoeksthema's van 'Minimum-link paths among obstacles in the plane'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit