Polyhedral Assembly Partitioning with Infinite Translations


Assembly partitioning with an infinite translation is the application of an infinite translation to partition an assembled product into two complementing subsets of parts,

Polyhedral Assembly Partitioning with Infinite Translations
Split Star Assembly

referred to as a subassemblies, each treated as a rigid body. We present an exact implementation of an efficient algorithm, based on the general framework designed by Halperin, Latombe, and Wilson, to obtain such a motion and subassemblies given an assembly of polyhedra in R3. We do not assume general position.

Namely, we can handle degenerate input, and we produce exact results. As often occurs, motions that partition a given assembly or subassembly might be isolated in the infinite space of motions. Any perturbation of the input or of intermediate results, caused by, for example, imprecision, might result with dismissal of valid partitioning-motions. In the extreme case where there is only a finite number of valid partitioning-motions, as occurs in the assembly shown to the right, no motion may be found, even though such exists. Proper handling requires significant enhancements applied to the original algorithmic framework.

The implementation is based on software components that have been developed and introduced only recently. They paved the way to a complete, efficient, and elegant implementation. Additional information about some of these components is available at Arrangement of Geodesic Arcs on a Sphere project page.

Split star assembly divided into three pairs of symmetric parts


The eight partitioning directionsof the split star assembly
The eight partitioning directions
of the split star assembly
Motion space arrangementof the split star assembly
Motion space arrangement
of the split star assembly



  • Efi Fogel and Dan Halperin
    Polyhedral Assembly Partitioning with Infinite Translations or The Importance of Being Exact
    IEEE TASE Automation Science and Engineering, 10(2): 227-241, 2013 [link] [bibtex]
    In H. Choset, M. Morales, and T. D. Murphey, editors, Algorithmic Foundations of Robotics VIII, volume 57 of Springer Tracks in Advanced Robotics, pages 417-432, Springer, Heidelberg, Germany, 2009 [link]
  • Efi Fogel
    Minkowski Sum Construction and other Applications of Arrangements of Geodesic Arcs on the Sphere

    PhD Thesis, Tel Aviv University, March 2008


Efi Fogel
Dan Halperin

Yair Oz - Webcreator


Skip to content