On translational motion planning in 3-space

Boris Aronov, Micha Sharir

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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 = l,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log2 k), where n is the total complexity of the individual Minkowski sums P1,..., Pk. The bound is almost tight in the worst case. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log3 k).

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual Symposium on Computational Geometry
    PublisherPubl by ACM
    Pages21-30
    Number of pages10
    ISBN (Print)0897916484, 9780897916486
    DOIs
    StatePublished - 1994
    EventProceedings of the 10th Annual Symposium on Computational Geometry - Stony Brook, NY, USA
    Duration: Jun 6 1994Jun 8 1994

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry

    Other

    OtherProceedings of the 10th Annual Symposium on Computational Geometry
    CityStony Brook, NY, USA
    Period6/6/946/8/94

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics

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

  • Cite this

    Aronov, B., & Sharir, M. (1994). On translational motion planning in 3-space. In Proceedings of the Annual Symposium on Computational Geometry (pp. 21-30). (Proceedings of the Annual Symposium on Computational Geometry). Publ by ACM. https://doi.org/10.1145/177424.177445