Piecewise linear paths among convex obstacles

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

    Research output: Contribution to journalArticleAcademicpeer-review

    7 Citations (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.
    Original languageEnglish
    Pages (from-to)9-29
    Number of pages21
    JournalDiscrete and Computational Geometry
    Issue number1
    Publication statusPublished - 1995


    Dive into the research topics of 'Piecewise linear paths among convex obstacles'. Together they form a unique fingerprint.

    Cite this