Minkowskisum

Minkowskisum, commonly referred to as the Minkowski sum, is a mathematical construction that combines two subsets of a Euclidean space into a new set. If A and B are subsets of R^n, their Minkowski sum is defined as A + B = {a + b | a ∈ A, b ∈ B}. The concept is named after Hermann Minkowski and is fundamental in convex geometry and related fields.

The Minkowski sum has several basic properties. It is commutative and associative: A + B = B + A and A + (B + C) = (A + B) + C. If A and B are convex, their sum is convex as well. If A and B are compact, their sum is compact. The operation interacts nicely with scaling: for any scalar t ≥ 0, tA + tB = t(A + B). An important tool is the support function h_{A+B}(u) = h_A(u) + h_B(u) for all directions u, which reflects how the sum behaves in every direction.

A simple example: the sum of two intervals in R, [0,1] + [0,2], equals [0,3]. In higher dimensions, the Minkowski sum describes how shapes combine under vector addition, such as adding a disk to a polygon or combining two polytopes.

Applications span several areas. In robotics and computer vision, Minkowski sums are used to model configuration space obstacles and to perform collision checking. In computer graphics and CAD, they support offsetting and buffering shapes. In image processing, dilation with a structuring element is a special case of the Minkowski sum. Computationally, sums of polytopes can be formed by combining support representations or vertex/facet representations, with algorithmic considerations depending on dimension and structure.