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
- <math>A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}<math>
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.