On two-handed planar assembly partitioning with connectivity constraints

Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin

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


    Assembly planning is a fundamental problem in robotics and automation, which aims to design a sequence of motions that brings the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected. In this paper we study a natural special case of the connected-assembly-partitioning problem: Given a connected set A of unit-grid squares in the plane, find a connected subset S ⊂ A such that A \ S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A \ S. We show that even this simple problem is NP-complete, settling an open question posed by Wilson et al. a quarter of a century ago [16]. We complement the hardness result with two positive results. First, we show that the problem is fixed-parameter tractable and present an O(2kn2)-time algorithm, where n = |A| and k = |S|. Second, we describe a special case of this problem where a connected partition can always be found in O(n) time.

    Original languageEnglish (US)
    Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
    EditorsDaniel Marx
    PublisherAssociation for Computing Machinery
    Number of pages17
    ISBN (Electronic)9781611976465
    StatePublished - 2021
    Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
    Duration: Jan 10 2021Jan 13 2021

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


    Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
    Country/TerritoryUnited States
    CityAlexandria, Virtual

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'On two-handed planar assembly partitioning with connectivity constraints'. Together they form a unique fingerprint.

    Cite this