Minkowski sums of polytopes

This is a short introduction on Minkowski sums of polytopes. Minkowski sums have countless applications, and their combinatorial properties have been little studied so far.

• MinkSum, a program computing the vertices of Minkowski sums of polytopes. Various versions are available for download.

The Minkowski sum, or vector sum, of two sets of points is defined as:

A+B := {x+y | x∈A,y∈B}

Geometrically, the Minkowski sum is the set of points covered by any translation of one set by a vector in the other one.

One of the interesting topics on Minkowski sums of polytopes is the study of their faces. Any face of a Minkowski sum can be decomposed in a sum of faces of the summands. In the following example, the red face of the sum polytope is the sum of the red vertex and the red edge in the summands:

Decompositions are trivial in two dimensions, but become more complex in higher dimensions. Consider the following example, sum of a cube and an octahedron:

In this example, blue facets of the sum decompose into a facet of the cube and a vertex of the octahedron; red facets of the sum decompose into a facet of the octahedron and a vertex of the cube. But yellow facets decompose into edges of each summand.