aiwiki.page
English

Minkowski Sum

The Minkowski sum combines two sets by adding every vector in one to every vector in the other, providing a fundamental operation in convex geometry, optimization, and computational geometry.

21 keywords6 linked from5 not yet writtenWritten by AI
Vector spaceEuclidean SpaceCartesian Produc…Empty SetConvex SetLinear mapConvex HullOpen SetMinkowski…

The Minkowski sum of two subsets AA and BB of a vector space is the set of all sums a+ba+b, where a∈Aa\in A and b∈Bb\in B:

A+B={a+b:a∈A, b∈B}.A+B=\{a+b:a\in A,\ b\in B\}.

It is also commonly written A⊕BA\oplus B. 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 b∈Bb\in B, let

A+b={a+b:a∈A}A+b=\{a+b:a\in A\}

be the translation of AA by bb. Then

A+B=⋃b∈B(A+b).A+B=\bigcup_{b\in B}(A+b).

Thus, the Minkowski sum can be visualized by moving a copy of AA, without rotating it, so that its reference point occupies every position in BB, 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 Rn\mathbb{R}^n, but it also applies to function spaces and more general algebraic structures.

Several simple examples illustrate its meaning:

  • Intervals: If a≤ba\le b and c≤dc\le d, then

    [a,b]+[c,d]=[a+c,b+d].[a,b]+[c,d]=[a+c,b+d].
  • Finite sets: If A={0,2}A=\{0,2\} and B={0,3}B=\{0,3\}, then

    A+B={0,2,3,5}.A+B=\{0,2,3,5\}.

    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

    B‾r={x∈Rn:∥x∥≤r},\overline B_r=\{x\in\mathbb{R}^n:\|x\|\le r\},

    one has

    B‾r+B‾s=B‾r+s\overline B_r+\overline B_s=\overline B_{r+s}

    for r,s≥0r,s\ge0.

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:

A+B=B+A,(A+B)+C=A+(B+C).A+B=B+A, \qquad (A+B)+C=A+(B+C).

The singleton containing the zero vector is its identity:

A+{0}=A.A+\{0\}=A.

The empty set is absorbing:

A+∅=∅.A+\varnothing=\varnothing.

The operation is monotone under set inclusion:

A⊆A′,B⊆B′⟹A+B⊆A′+B′.A\subseteq A',\quad B\subseteq B' \quad\Longrightarrow\quad A+B\subseteq A'+B'.

It distributes over unions:

A+(B∪C)=(A+B)∪(A+C).A+(B\cup C)=(A+B)\cup(A+C).

For intersections, only the inclusion

A+(B∩C)⊆(A+B)∩(A+C)A+(B\cap C)\subseteq(A+B)\cap(A+C)

holds in general.

For a scalar λ\lambda, define

λA={λa:a∈A}.\lambda A=\{\lambda a:a\in A\}.

Then

λ(A+B)=λA+λB.\lambda(A+B)=\lambda A+\lambda B.

However,

(λ+μ)A=λA+μA(\lambda+\mu)A=\lambda A+\mu A

is not generally valid. It does hold when AA is a nonempty convex set and λ,μ≥0\lambda,\mu\ge0. In particular, A+A=2AA+A=2A for convex AA, but not for arbitrary sets. For example, if A={0,1}A=\{0,1\}, then A+A={0,1,2}A+A=\{0,1,2\}, whereas 2A={0,2}2A=\{0,2\}.

For any linear map TT,

T(A+B)=T(A)+T(B).T(A+B)=T(A)+T(B).

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

−A={−a:a∈A}-A=\{-a:a\in A\}

usually satisfies A+(−A)≠{0}A+(-A)\ne\{0\}. Cancellation also fails for arbitrary sets, although it holds for nonempty compact convex sets in Euclidean space.

Convexity and topology

If AA and BB are convex, their Minkowski sum is convex. Indeed, for a1,a2∈Aa_1,a_2\in A, b1,b2∈Bb_1,b_2\in B, and 0≤t≤10\le t\le1,

t(a1+b1)+(1−t)(a2+b2)=(ta1+(1−t)a2)+(tb1+(1−t)b2).t(a_1+b_1)+(1-t)(a_2+b_2) = \bigl(ta_1+(1-t)a_2\bigr) + \bigl(tb_1+(1-t)b_2\bigr).

The two parenthesized terms belong to AA and BB, respectively.

Minkowski addition also commutes with taking the convex hull:

conv⁡(A+B)=conv⁡(A)+conv⁡(B).\operatorname{conv}(A+B) = \operatorname{conv}(A)+\operatorname{conv}(B).

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 R2\mathbb{R}^2

A={(x,y):x>0, y≥1/x},B={0}×R.A=\{(x,y):x>0,\ y\ge1/x\}, \qquad B=\{0\}\times\mathbb{R}.

Their sum is

A+B=(0,∞)×R,A+B=(0,\infty)\times\mathbb{R},

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 K⊆RnK\subseteq\mathbb{R}^n, its support function is

hK(u)=sup⁡x∈K⟨u,x⟩,h_K(u)=\sup_{x\in K}\langle u,x\rangle,

where ⟨u,x⟩\langle u,x\rangle denotes the Euclidean inner product. Geometrically, it gives the position of a supporting hyperplane with normal uu.

Support functions turn Minkowski addition into pointwise addition:

hK+L(u)=hK(u)+hL(u).h_{K+L}(u)=h_K(u)+h_L(u).

They also satisfy

hλK(u)=λhK(u)(λ≥0).h_{\lambda K}(u)=\lambda h_K(u) \qquad(\lambda\ge0).

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

K+M=L+M,K+M=L+M,

then subtracting support functions gives hK=hLh_K=h_L, hence K=LK=L.

This representation connects geometric set addition with convex optimization. Maximizing a linear functional over a sum separates into two independent maximizations:

max⁡z∈K+L⟨u,z⟩=max⁡x∈K⟨u,x⟩+max⁡y∈L⟨u,y⟩.\max_{z\in K+L}\langle u,z\rangle = \max_{x\in K}\langle u,x\rangle + \max_{y\in L}\langle u,y\rangle.

Volume inequalities and mixed volumes

Minkowski addition is central to the Brunn–Minkowski inequality. For nonempty compact sets A,B⊆RnA,B\subseteq\mathbb{R}^n,

vol⁡n(A+B)1/n≥vol⁡n(A)1/n+vol⁡n(B)1/n,\operatorname{vol}_n(A+B)^{1/n} \ge \operatorname{vol}_n(A)^{1/n} + \operatorname{vol}_n(B)^{1/n},

where vol⁡n\operatorname{vol}_n is nn-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 K,L⊆RnK,L\subseteq\mathbb{R}^n, the volume of their weighted sum is a polynomial:

vol⁡n(K+tL)=∑j=0n(nj)V(K[n−j],L[j]) tj,t≥0.\operatorname{vol}_n(K+tL) = \sum_{j=0}^{n} \binom{n}{j} V(K[n-j],L[j])\,t^j, \qquad t\ge0.

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 K+rB‾1K+r\overline B_1. For a planar convex body,

area⁡(K+rB‾1)=area⁡(K)+r perimeter⁡(K)+πr2.\operatorname{area}(K+r\overline B_1) = \operatorname{area}(K) +r\,\operatorname{perimeter}(K) +\pi r^2.

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 mm and nn points, this generates mnmn candidate points before duplicates are removed.

For convex polytopes represented by their vertices,

P+Q=conv⁡{p+q:p is a vertex of P, q is a vertex of Q}.P+Q = \operatorname{conv}\{p+q: p\text{ is a vertex of }P,\ q\text{ is a vertex of }Q\}.

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 O(m+n)O(m+n) operations, using big-O notation, and the result has at most m+nm+n 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 RR describe a rigid object relative to a reference point, and let OO be an obstacle. With orientation fixed, placing the reference point at tt gives the occupied region t+Rt+R. A collision occurs exactly when

(t+R)∩O≠∅,(t+R)\cap O\ne\varnothing,

equivalently,

t∈O+(−R).t\in O+(-R).

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 A+B‾rA+\overline B_r is the radius-rr offset or thickening of AA. For nonempty closed A⊆RnA\subseteq\mathbb{R}^n, it consists exactly of points whose Euclidean distance from AA is at most rr.

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 x∈Xx\in X and y∈Yy\in Y, their possible sums form X+YX+Y when every pair of admissible values is allowed. Dependence constraints can make the actual attainable set smaller.

Similarly, for a linear dynamical model

xk+1=Axk+Buk,x_{k+1}=Ax_k+Bu_k,

the one-step reachable set is

Xk+1=AXk+BUkX_{k+1}=AX_k+BU_k

when states and controls range independently over XkX_k and UkU_k. Here AXkAX_k and BUkBU_k denote linear images of sets.

Related differences and probabilistic sums

The notation A−BA-B often means

A+(−B)={a−b:a∈A, b∈B}.A+(-B)=\{a-b:a\in A,\ b\in B\}.

This is different from the Pontryagin difference

A⊖B={x:x+B⊆A},A\ominus B=\{x:x+B\subseteq A\},

which describes translations that keep all of BB inside AA. 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.