minkowski addition

In geometry, the Minkowski sum of two sets A and B in Euclidean space is the result of adding every element of A to every element of B, i.e. the set

A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}

For example, if we have two 2-simplices (triangles), with points represented by

A = {(1, 0), (0, 1), (0, -1)}

and

B = {(0, 0), (1, 1), (1, -1)},

then the Minkowski sum is

A+B = {(1, 0), (2, 1), (2, -1), (0, 1), (1, 2), (1, 0), (0, -1), (1, 0), (1, -2)},

which looks like a hexagon, with three 'repeated' points at (1,0). This defines a binary operation called Minkowski addition, named after Hermann Minkowski. It occurs in a basic step in proving Minkowski's theorem, in the form

C + C = 2C

for a convex symmetric set containing 0, where the left-hand side is the Minkowski sum and the right-hand side the enlargement by a factor of 2. This operation is sometimes called (somewhat inappropriately) the convolution of the two sets. The actual convolution of the indicator functions of the set will be a function with the same support as the Minkowski sum. Minkowski addition is also called the binary dilation of A by B. Minkowski addition plays a central role in mathematical morphology. It arises in the brush-and-stroke paradigm of 2D computer graphics (pioneered by Donald E. Knuth in Metafont), and as the solid sweep operation of 3D computer graphics.

Minkowski Addition

See also