On translational motion planning of a convex polyhedron in 3-space

Boris Aronov, Micha Sharir

    Research output: Contribution to journalArticlepeer-review


    Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,..., Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums Pi = Ai ⊕ (-B), for i = 1,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log k), and that it can be Ω(nkα(k)) in the worst case, where n is the total complexity of the individual Minkowski sums P1,...,Pk. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log k log n).

    Original languageEnglish (US)
    Pages (from-to)1785-1803
    Number of pages19
    JournalSIAM Journal on Computing
    Issue number6
    StatePublished - Dec 1997


    • Algorithmic motion planning
    • Combinatorial complexity
    • Combinatorial geometry
    • Computational geometry
    • Convex polyhedra
    • Geometric algorithms
    • Randomized algorithms

    ASJC Scopus subject areas

    • General Computer Science
    • General Mathematics


    Dive into the research topics of 'On translational motion planning of a convex polyhedron in 3-space'. Together they form a unique fingerprint.

    Cite this