Piecewise linear paths among convex obstacles

M. Berg, de, J. Matousek, O. Schwarzkopf

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    7 Citaten (Scopus)
    10 Downloads (Pure)


    Let B be a set ofn arbitrary (possibly intersecting) convex obstacles in R d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n (d-1)[d/2+1]) segments. The bound cannot be improved below O(n d ); thus, in R3, the answer is betweenn 3 andn 4. For open disjoint convex obstacles, a T(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case.
    Originele taal-2Engels
    Pagina's (van-tot)9-29
    Aantal pagina's21
    TijdschriftDiscrete and Computational Geometry
    Nummer van het tijdschrift1
    StatusGepubliceerd - 1995


    Duik in de onderzoeksthema's van 'Piecewise linear paths among convex obstacles'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit