MinkowskiSummen

Minkowski sum is an operation on subsets of a vector space. For two sets A and B in R^n, the Minkowski sum is defined as A + B = {a + b | a in A, b in B}. It is a fundamental tool in geometry, convex analysis, and related fields.

Basic properties include commutativity and associativity: A + B = B + A and (A + B) + C = A + (B + C). If A and B are convex, their sum is convex; if they are compact, the sum is compact. Translating a set by a vector t satisfies A + {t}. A useful functional relation is that the support function satisfies h_{A+B}(u) = h_A(u) + h_B(u) for all directions u, linking the sum to directional extent.

For polytopes and convex bodies, the Minkowski sum is again a polytope or convex body. If A = conv(V) and B = conv(W) are convex hulls of vertex sets V and W, then A + B = conv({v + w | v in V, w in W}). This provides a practical route to computation from vertex representations. When represented by half-spaces (inequalities), polyhedral operations can be used to compute the sum, though this may be more involved.

Examples help illustrate the idea. In one dimension, [0,1] + [0,2] equals [0,3]. In two dimensions, [0,1]×[0,1] plus itself yields [0,2]×[0,2]. More generally, the sum expands figures by combining their extents in all directions.

Applications span robot motion planning, where Minkowski sums describe configuration-space obstacles, computer graphics and image processing (morphological dilation), and convex optimization, where support functions and duality leverage the operation. See also convex hull, support function, and polytope.