Minkowski addition
From Wikipedia, the free encyclopedia
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
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.
