Personal tools
You are here: Home Projects Assembly Partitioning
« February 2023 »
Log in

Forgot your password?

Polyhedral Assembly Partitioning with Infinite Translations

split star
Split Star Assembly
split star red green split star blue purple split star turqouise-yellow
Split star assembly divided into three pairs of symmetric parts



 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 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 solution split star ndbg
The eight partitioning directions
of 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] [bibtex]

  • Efi Fogel
    Minkowski Sum Construction and other Applications of Arrangements of Geodesic Arcs on the Sphere

    PhD Thesis, Tel Aviv University, March 2008 [pdf] [bibtex]


Efi Fogel
Dan Halperin
Document Actions