Efi Fogel
home 
contact
 
search
 
[2D][3D][Arrangements]
4_4_4 primal4_4_4 dual
The figure on the left shows the Minkowski sum of three tetrahedra rotated about the Y axis 0, 60120 respectively, and the Gaussian map of the Minkowski sum. The tetrahedra are constructed to maxmize the number of facets in the Minkowski sum, which is the number of vertices in its dual Gaussian map. You can view the individual summands and their Minkowski sums, the primal shapes and the dual Gaussian maps, using the player interactive program.

We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in 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 3. That is, given k positive integers m_1,m_2,...,m_k, we describe how to construct k convex polyhedra with corresponding number of facets, such that the number of facets of their Minkowski sum is exactly 1 i < j k(2mi - 5)(2mj - 5) + binom(k,2). We also provide a conservative upper bound for the general case.

The figure on the right is a snapshot of a simulation and demonstration program that detects collision in 3 between a static 3D obstacle P (a dioctagonal pyramid in the figure), and a moving 3D robot Q (an icosahedron in the figure). The program draws the obstacle and the trail of the robot. The Minkowski sum P -Q is recomputed only when the robot is rotated, which occurs every other frame. The program is able to identify the case where the robot grazes the obstacle, but does not penetrate it. The computation takes just a fraction of a second on a Pentium PC clocked at 1.8 GHz.
The figure on the left is a snapshot of the same program executed in interactive mode. In this mode The program opens a window divided into four quadrants. The bottom left is the work space. It contains two polytopes; a robot and an obstacle (A pentagonal hexecontahedron and a truncated icosidodecahedron in the figure). The bootom right quadrant is the auxiliary space. It shows the obstacle and the reflected robot. The top left quadrant is the configuration space. It shows the origin and the Minkowski sum of the obstacle and the reflected robot. The top right quadrant shows the folded unit-cube of the cubical Gaussian map. Each face of the unit cube is associated with a planar map. The blue segments originate from the robot and the red segments originate from the obstacle.

Last modified: December 11 2006.
2D 3D AOS