Minkowski sum A + B
B
A
In
geometry, the
Minkowski sum — also known as dilation — 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.
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
Thus, the
essential Minkowski sum is defined by
where
μ denotes
n-dimensional
Lebesgue measure. The reason for the term "essential" is the following property of
indicator functions: while
it can be seen that
where ess sup denotes the
essential supremum.
Applications
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.
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.
NC machining
In
NC 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.
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 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)
Special case defined by monotone polygons.
Let P be a simple polygon with m edges, which is the disjoint union of k simple polygons, all monotone in a common direction u, and let Q be another simple polygon with n edges, which is the disjoint union of ℓ simple polygons, all monotone in a common direction v. We show that the combinatorial complexity of the Minkowski sum P ⊕ Q is O(kℓmnα(min{m,n})), where α(·) is the inverse Ackermann function. Some structural properties of the case k = ℓ = 1 have been (implicitly) studied in [17]. We rederive these properties using a different proof, apply them to obtain the above complexity bound for k = ℓ = 1, obtain several additional properties of the sum for this special case, and then use them to derive the general bound.
See also
