In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors
A and B in Euclidean space is formed by adding each vector in A to each vector in B, i.e.,
the set
A +
B =
{
a
+
b
|
a
∈ A
,
b
∈ B
} .
{\displaystyle A+B=\{\mathbf {a} +\mathbf {b} \,|\,\mathbf {a} \in A,\ \mathbf {b} \in
B\}.} Analogously, the Minkowski difference (or
geometric difference) is defined as
A −
B =
{
c
|
c
+ B
⊆ A
} .
{\displaystyle A-B=\{\mathbf {c} \,|\,\mathbf {c} +B\subseteq A\}.}
It is important to note that in general
A −
B ≠
A +
( −
B )
. For instance, in a one-dimensional case
A =
[ −
2 ,
2 ]
and
B =
[ −
1 ,
1 ]
the Minkowski difference
A −
B =
[ −
1 ,
1 ]
, whereas
A +
( −
B )
= A
+ B
= [
− 3
, 3
] .
The correct formula connecting Minkowski sum
and difference is as follows (here
X
c
{\displaystyle X^{c}} stands for the complement of
X
):
A −
B =
(
A
c
+ (
− B
)
c
.
{\displaystyle A-B=(A^{c}+(-B))^{c}.} In a two-dimensional case, Minkowski difference
is closely related to erosion (morphology) in image processing.
The concept is named for Hermann Minkowski.
== Example == For example, if we have two sets A and B,
each consisting of three position vectors (informally, three points), representing the
vertices of two triangles in
R
2
{\displaystyle \mathbb {R} ^{2}} , with coordinates
A =
{ (
1 ,
0 )
, (
0 ,
1 )
, (
0 ,
− 1
) }
{\displaystyle A=\{(1,0),(0,1),(0,-1)\}} and
B =
{ (
0 ,
0 )
, (
1 ,
1 )
, (
1 ,
− 1
) }
,
{\displaystyle B=\{(0,0),(1,1),(1,-1)\},} then their Minkowski sum is
A +
B =
{ (
1 ,
0 )
, (
2 ,
1 )
, (
2 ,
− 1
) ,
( 0
, 1
) ,
( 1
, 2
) ,
( 0
, −
1 )
, (
1 ,
− 2
) }
,
{\displaystyle A+B=\{(1,0),(2,1),(2,-1),(0,1),(1,2),(0,-1),(1,-2)\},} which comprises the vertices of a hexagon.
For Minkowski addition, the zero set, {0}, containing only the zero vector, 0, is an
identity element: for every subset S of a vector space,
S +
{ 0
} =
S .
{\displaystyle S+\{0\}=S.} The empty set is important in Minkowski addition,
because the empty set annihilates every other subset: for every subset S of a vector space,
its sum with the empty set is empty:
S +
∅ =
∅ .
== Convex hulls of Minkowski sums == Minkowski addition behaves well with respect
to the operation of taking convex hulls, as shown by the following proposition:
For all non-empty subsets S1 and S2 of a real vector space, the convex hull of their Minkowski
sum is the Minkowski sum of their convex hulls:
Conv ⁡
(
S
1
+
S
2
) =
Conv ⁡
(
S
1
) +
Conv ⁡
(
S
2
) .
{\displaystyle \operatorname {Conv} (S_{1}+S_{2})=\operatorname {Conv} (S_{1})+\operatorname {Conv} (S_{2}).}
This result holds more generally for any finite collection of non-empty sets:
Conv ⁡
(
∑
S
n
)
= ∑
Conv ⁡
(
S
n
) .
{\displaystyle \operatorname {Conv} \left(\sum {S_{n}}\right)=\sum \operatorname {Conv} (S_{n}).}
In mathematical terminology, the operations of Minkowski summation and of forming convex
hulls are commuting operations.If S is a convex set then
μ S
+ λ
S
is also a convex set; furthermore
μ S
+ λ
S =
( μ
+ λ
) S
for every
μ ,
λ ≥
0
. Conversely, if this "distributive property"
holds for all non-negative real numbers,
μ ,
λ
, then the set is convex.The figure shows
an example of a non-convex set for which A + A ⊋ 2A.
An example in 1 dimension is: B=[1,2]∪[4,5]. It can be easily calculated that 2B=[2,4]∪[8,10]
but B+B=[2,4]∪[5,7]∪[8,10], hence again B+B ⊋ 2B.
Minkowski sums act linearly on the perimeter of two-dimensional convex bodies: the perimeter
of the sum equals the sum of perimeters. Additionally, if K is (the interior of) a curve of constant
width, then the Minkowski sum of K and of its 180° rotation is a disk. These two facts
can be combined to give a short proof of Barbier's theorem on the perimeter of curves of constant
width.
== Applications == Minkowski addition plays a central role in
mathematical morphology. It arises in the brush-and-stroke paradigm of 2D computer graphics
(with various uses, notably by Donald E. Knuth in Metafont), and as the solid sweep operation
of 3D computer graphics.
=== Motion planning === Minkowski sums are used in motion planning
of an object among obstacles. They are used for the computation of the configuration space,
which is the set of all admissible positions of the object. In the simple model of translational
motion of an object in the plane, where the position of an object may be uniquely specified
by the position of a fixed point of this object, the configuration space are the Minkowski
sum of the set of obstacles and the movable object placed at the origin and rotated 180
degrees.
=== Numerical control (NC) machining === In numerical control machining, the programming
of the NC tool exploits the fact that the Minkowski sum of the cutting piece with its
trajectory gives the shape of the cut in the material.
=== 3d Solid Modeling === In OpenSCAD Minkowski sums are used to outline
a shape with another shape creating a composite of both shapes.
=== Aggregation Theory === Minkowski sums are also frequently used in
aggregation theory when individual objects to be aggregated are characterized via sets.
== Algorithms for computing Minkowski sums ==
=== Planar case ===
==== Two convex polygons in the plane ==== For two convex polygons P and Q in the plane
with m and n vertices, their Minkowski sum is a convex polygon with at most m + n vertices
and may be computed in time O (m + n) by a very simple procedure, which may be informally
described as follows. Assume that the edges of a polygon are given and the direction,
say, counterclockwise, along the polygon boundary. Then it is easily seen that these edges of
the convex polygon are ordered by polar angle. Let us merge the ordered sequences of the
directed edges from P and Q into a single ordered sequence S. Imagine that these edges
are solid arrows which can be moved freely while keeping them parallel to their original
direction. Assemble these arrows in the order of the sequence S by attaching the tail of
the next arrow to the head of the previous arrow. It turns out that the resulting polygonal
chain will in fact be a convex polygon which is the Minkowski sum of P and Q.
==== Other ==== If one polygon is convex and another one is
not, the complexity of their Minkowski sum is O(nm). If both of them are nonconvex, their
Minkowski sum complexity is O((mn)2).
== Essential Minkowski sum == There is also a notion of the essential Minkowski
sum +e of two subsets of Euclidean space. Note that the usual Minkowski sum can be written
as
A +
B =
{ z
∈
R
n
|
A ∩
( z
− B
) ≠
∅ }
.
{\displaystyle A+B=\{z\in \mathbb {R} ^{n}\,|\,A\cap (z-B)\neq \emptyset \}.}
Thus, the essential Minkowski sum is defined by
A
+
e
B =
{ z
∈
R
n
|
μ
[
A ∩
( z
− B
)
]
> 0
} ,
{\displaystyle A+_{\mathrm {e} }B=\{z\in \mathbb {R} ^{n}\,|\,\mu \left[A\cap (z-B)\right]>0\},}
where μ denotes the n-dimensional Lebesgue measure. The reason for the term "essential"
is the following property of indicator functions: while
1
A
+
B
( z
) =
sup
x
∈
R
n
1
A
( x
)
1
B
( z
− x
) ,
{\displaystyle 1_{A\,+\,B}(z)=\sup _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}
it can be seen that
1
A
+
e
B
( z
) =
e s
s
s u
p
x
∈
R
n
⁡
1
A
( x
)
1
B
( z
− x
) ,
{\displaystyle 1_{A\,+_{\mathrm {e} }\,B}(z)=\mathop {\mathrm {ess\,sup} } _{x\,\in \,\mathbb {R}
^{n}}1_{A}(x)1_{B}(z-x),} where "ess sup" denotes the essential supremum.
== Lp Minkowski sum == For K and L compact convex subsets in
R
n
{\displaystyle \mathbb {R} ^{n}} , the Minkowski sum can be described by the
support function of the convex sets:
h
K +
L
=
h
K
+
h
L
.
{\displaystyle h_{K+L}=h_{K}+h_{L}.} For p ≥ 1, Firey defined the Lp Minkowski
sum K+pL of compact convex sets K and L in
R
n
{\displaystyle \mathbb {R} ^{n}} containing the origin as
h
K
+
p
L
p
=
h
K
p
+
h
L
p
.
{\displaystyle h_{K+_{p}L}^{p}=h_{K}^{p}+h_{L}^{p}.} By the Minkowski inequality, the function
hK+pL is again positive homogeneous and convex and hence the support function of a compact
convex set. This definition is fundamental in the Lp Brunn-Minkowski theory.
== See also == Dilation
Erosion Interval arithmetic
Mixed volume (a.k.a. Quermassintegral or intrinsic volume)
Parallel curve Shapley–Folkman lemma
Zonotope Convolution
== Notes