Close this search box.

Polyhedral Assembly Partitioning with Infinite Translations


Polyhedral Assembly Partitioning with Infinite Translations
Split Star Assembly

Assembly partitioning with an infinite translation is the application of an infinite translation to partition an assembled product into two complementing subsets of parts, 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 \(\mathbb{R}^3\). 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]
    Algorithmic Foundations of Robotics VIII, volume 57 of Springer Tracks in Advanced Robotics, pages 417-432, Springer, Heidelberg, Germany, 2009 [link][bibtex]
  • Efi Fogel
    Minkowski Sum Construction and other Applications of Arrangements of Geodesic Arcs on the Sphere

    Ph.D. Thesis, Tel Aviv University, March 2008 [pdf][bibtex]


Efi Fogel
Dan Halperin

Yair Oz - Webcreator


Skip to content