The Minkowski sum of two subsets and of a vector space is the set of all sums , where and :
It is also commonly written . Named after the mathematician Hermann Minkowski, this operation turns vector addition into an operation on entire sets. It is fundamental in convex geometry and is used to describe geometric offsets, combine uncertainty regions, and compute collision constraints.
Definition and geometric interpretation
For each , let
be the translation of by . Then
Thus, the Minkowski sum can be visualized by moving a copy of , without rotating it, so that its reference point occupies every position in , and taking the union of all resulting copies.
The operation is defined whenever the ambient space has an addition law. Its most familiar setting is Euclidean space , but it also applies to function spaces and more general algebraic structures.
Several simple examples illustrate its meaning:
Intervals: If and , then
Finite sets: If and , then
Different pairs can yield the same sum, so the number of resulting elements need not equal the product of the input sizes.
Line segments: Two nonparallel line segments in the plane have a parallelogram as their sum.
Balls: Writing
one has
for .
A Minkowski sum is neither a union nor a Cartesian product. It combines points through addition rather than merely collecting them or forming ordered pairs.
Algebraic properties
Minkowski addition inherits commutativity and associativity from vector addition:
The singleton containing the zero vector is its identity:
The empty set is absorbing:
The operation is monotone under set inclusion:
It distributes over unions:
For intersections, only the inclusion
holds in general.
For a scalar , define
Then
However,
is not generally valid. It does hold when is a nonempty convex set and . In particular, for convex , but not for arbitrary sets. For example, if , then , whereas .
For any linear map ,
This allows sums to be projected or transformed by applying the same linear operation to their summands.
Minkowski addition does not generally provide additive inverses. The reflected set
usually satisfies . Cancellation also fails for arbitrary sets, although it holds for nonempty compact convex sets in Euclidean space.
Convexity and topology
If and are convex, their Minkowski sum is convex. Indeed, for , , and ,
The two parenthesized terms belong to and , respectively.
Minkowski addition also commutes with taking the convex hull:
Consequently, convexifying the inputs and then adding produces the convex hull of the exact sum. It can nevertheless fill holes or gaps present in a nonconvex sum.
Topological properties require some care:
- The sum of two compact sets is compact, because addition is a continuous map on their product.
- The sum of an open set and any set is open.
- In Euclidean space, the sum of a compact set and a closed set is closed.
- Two closed sets can have a sum that is not closed.
For the last point, consider the closed subsets of
Their sum is
which is not closed. This example also shows that closedness can fail even when both summands are convex.
Support functions and convex bodies
For a nonempty compact convex set , its support function is
where denotes the Euclidean inner product. Geometrically, it gives the position of a supporting hyperplane with normal .
Support functions turn Minkowski addition into pointwise addition:
They also satisfy
A nonempty compact convex set is uniquely determined by its support function. Therefore, these identities encode Minkowski addition exactly within that class. They also prove cancellation: if
then subtracting support functions gives , hence .
This representation connects geometric set addition with convex optimization. Maximizing a linear functional over a sum separates into two independent maximizations:
Volume inequalities and mixed volumes
Minkowski addition is central to the Brunn–Minkowski inequality. For nonempty compact sets ,
where is -dimensional Lebesgue measure.
The inequality expresses a lower bound on volume growth under set addition. Among convex bodies with nonempty interior, equality occurs precisely when the bodies are translates of positive scalar multiples of one another.
For compact convex sets , the volume of their weighted sum is a polynomial:
The coefficients are mixed volumes; the bracketed notation specifies how many times each set occurs as an argument.
A particularly useful case is the offset . For a planar convex body,
This is the planar form of Steiner’s formula, relating Minkowski addition to area and perimeter.
Computation
For finite point sets, a direct method forms all pairwise sums. If the sets contain and points, this generates candidate points before duplicates are removed.
For convex polytopes represented by their vertices,
Not every pairwise vertex sum is a vertex of the result.
In two dimensions, convex polygons admit a more efficient construction. When their vertices are listed in cyclic order, the boundary edge vectors of the sum can be obtained by merging the two cyclic sequences of edge directions. With suitable starting vertices, this takes operations, using big-O notation, and the result has at most edges.
Nonconvex inputs are more difficult: their sum can have holes and substantially more boundary structure. A common method decomposes the inputs into convex pieces, computes sums of pairs of pieces, and takes their union. In higher dimensions, output complexity can itself become large, limiting the efficiency of explicit representations.
Applications
Motion planning and collision detection
Let describe a rigid object relative to a reference point, and let be an obstacle. With orientation fixed, placing the reference point at gives the occupied region . A collision occurs exactly when
equivalently,
The sum therefore describes forbidden reference-point positions. This construction is fundamental in robot motion planning. If rotations are also allowed, an additional orientation parameter is required; one fixed Minkowski sum describes only the translational problem.
Offsets and mathematical morphology
The set is the radius- offset or thickening of . For nonempty closed , it consists exactly of points whose Euclidean distance from is at most .
In mathematical morphology, dilation by a structuring set is commonly defined through Minkowski addition. It is used in image processing to expand regions, bridge gaps, and model shape-dependent neighborhoods.
Uncertainty and reachable sets
If uncertain vectors satisfy and , their possible sums form when every pair of admissible values is allowed. Dependence constraints can make the actual attainable set smaller.
Similarly, for a linear dynamical model
the one-step reachable set is
when states and controls range independently over and . Here and denote linear images of sets.
Related differences and probabilistic sums
The notation often means
This is different from the Pontryagin difference
which describes translations that keep all of inside . Neither operation is a general inverse of Minkowski addition, and the meaning of “Minkowski difference” varies between fields.
Minkowski addition must also be distinguished from addition of probability distributions. The distribution of a sum of independent random vectors is described by convolution, which accounts for probability weights. A Minkowski sum records possible vector sums without assigning probabilities; for compactly supported independent random vectors, the support of their sum is the Minkowski sum of their supports.