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 subassemblies, each treated as a rigid body. We present an exact implementation of an efficient algorithm to obtain such a motion and subassemblies given an assembly of polyhedra in R3. We do not assume general position. Namely, we handle degenerate input, and 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, no motion may be found, even though such exists. The implementation is based on software components that have been developed and introduced only recently. They paved the way to a complete, efficient, and concise implementation. Additional information is available at http://acg.cs.tau.ac.il/projects/assembly-partitioning/project-page.

We present a novel method for fast retrieval of exact Minkowski sums of pairs of convex polytopes in R3, where one of the polytopes frequently rotates. The algorithm is based on pre-computing a so-called criticality map, which records the changes in the underlying graph-structure of the Minkowski sum, while one of the polytopes rotates. We give tight combinatorial bounds on the complexity of the criticality map when the rotating polytope rotates about one, two, or three axes. The criticality map can be rather large already for rotations about one axis, even for summand polytopes with a moderate number of vertices each. We therefore focus on the restricted case of rotations about a single, though arbitrary, axis.

This movie illustrates exact construction and maintenance of arrangements induced by arcs of great circles embedded on the sphere, also known as geodesic arcs, and exact computation of Voronoi diagrams on the sphere, the bisectors of which are geodesic arcs. This class of Voronoi diagrams includes the subclass of Voronoi diagrams of points and its generalization, power diagrams, also known as Laguerre Voronoi diagrams. The resulting diagrams are represented as arrangements, and can be passed as input to consecutive operations supported by the Arrangement_2 package of CGAL and its derivatives. The implementation handles well degenerate input and produces exact results.

We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in R 3. In particular, we prove that the maximum number of facets of the Minkowski sum of two convex polyhedra with m and n facets respectively is bounded from above by f(m, n) = 4mn−9m−9n+26. Given two positive integers m and n, we describe how to construct two convex polyhedra with m and n facets respectively, such that the number of facets of their Minkowski sum is exactly f(m, n). We generalize the construction to yield a lower bound on the maximum complexity of Minkowski sums of many convex polyhedra in R 3. That is, given k positive integers m1, m2,..., mk, we describe how to construct k convex polyhedra with corresponding number of facets, such that the number of facets of their Minkowski sum is P 1≤i

We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in ℝ3. Our implementation is complete in the sense that it does not assume general position. Namely, it can handle degenerate input, and it produces exact results. We also present applications of the Minkowski-sum computation to answer collision and proximity queries about the relative placement of two convex polyhedra in ℝ3. The algorithms use a dual representation of convex polyhedra, and their implementation is mainly based on the Arrangement package of Cgal, the Computational Geometry Algorithm Library. We compare our Minkowski-sum construction with the only three other methods that produce exact results we are aware of. One is a simple approach that computes the convex hull of the pairwise sums of vertices of two convex polyhedra. The second is based on Nef polyhedra embedded on the sphere, and the third is an output sensitive approach based on linear programming. Our method is significantly faster. The results of experimentation with a broad family of convex polyhedra are reported. The relevant programs, source code, data sets, and documentation are available at http://www.cs.tau.ac.il/∼efif/CD, and a short movie [16] that describes some of the concepts portrayed in this paper can be downloaded from http://www.cs.tau.ac.il/∼efif/CD/Mink3d.avi.

We present an exact imp ementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R3. Our implementation is complete in the sense that it does not assume general position, namely, it can handle degenerate input, and produces exact results. Our software also includes applications of the Minkowski-sum computation to answer collision and proximity queries about the relative placement of two convex polyhedra in R3. The algorithms use a dual representation of convex polyhedra,and their implementation is mainly based on the Arrangement package of Cgal the Computational Geometry Algorithm Library. We compare our Minkowski-sum construction with a naïve approach that computes the convex hull of the pairwise sums of vertices of two convex polyhedra.Our method is significantly faster. The video demonstrates the techniques used on simple cases as well as on degenerate cases. The relevant programs, source code, data sets, and documentation are available at http://www.cs.tau.ac.il/~efif/CD Inparticular this site contains a detailed report [3 ]on our algorithms and their implementation including the experimental comparison with the convex-hull approach.

(MATH) The Minkowski sum of two sets P and Q in $\realsd is the set (p+q \mid p Ε P, q Ε Q). Minkowski sums are useful in robot motion planning, computer-aided design and manufacturing (CAD/CAM) and many other areas. In this video we present a software package implemented at Tel Aviv University for the exact and efficient construction of Minkowski sums of planar sets. We also explain and demonstrate how Minkowski sums are used in various applications.