Incubator escapee wiki

Minkowski addition

Article Discussion
Revision as of 05:47, 8 January 2025 by imported>Est. 2021 (cleanup via script)
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Template:Short description

File:Сумма Минковского.svg
The red figure is the Minkowski sum of blue and green figures.

In geometry, the Minkowski sum of two sets of position vectors A and B in Euclidean space is formed by adding each vector in A to each vector in B:

<math display="block">A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}</math>

The Minkowski difference (also Minkowski subtraction, Minkowski decomposition, or geometric difference)<ref>Template:Citation</ref> is the corresponding inverse, where <math display="inline">(A - B)</math> produces a set that could be summed with B to recover A. This is defined as the complement of the Minkowski sum of the complement of A with the reflection of B about the origin.<ref>Template:Cite thesis</ref>

<math display="block">\begin{align} -B &= \{\mathbf{-b}\,|\,\mathbf{b}\in B\}\\ A - B &= (A^\complement + (-B))^\complement \end{align}</math>

This definition allows a symmetrical relationship between the Minkowski sum and difference. Note that alternately taking the sum and difference with B is not necessarily equivalent. The sum can fill gaps which the difference may not re-open, and the difference can erase small islands which the sum cannot recreate from nothing.

<math display="block">\begin{align} (A - B) + B &\subseteq A\\ (A + B) - B &\supseteq A\\ A - B &= (A^\complement + (-B))^\complement\\ A + B &= (A^\complement - (-B))^\complement\\ \end{align}</math>

In 2D image processing the Minkowski sum and difference are known as dilation and erosion.

An alternative definition of the Minkowski difference is sometimes used for computing intersection of convex shapes.<ref>Template:Cite journal</ref> This is not equivalent to the previous definition, and is not an inverse of the sum operation. Instead it replaces the vector addition of the Minkowski sum with a vector subtraction. If the two convex shapes intersect, the resulting set will contain the origin.

<math display="block">A - B = \{\mathbf{a}-\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\} = A + (-B)</math>

The concept is named for Hermann Minkowski.

ExampleEdit

File:Minkowski-sumex4.svg
Minkowski sum Template:Nowrap

For example, if we have two sets A and B, each consisting of three position vectors (informally, three points), representing the vertices of two triangles in <math display="inline">\mathbb{R}^2</math>, with coordinates

<math display="block">A = \{(1,0), (0,1), (0,-1)\}</math>

and

<math display="block">B = \{(0,0), (1,1), (1,-1)\}</math>

then their Minkowski sum is

<math display="block">A + B = \{(1,0), (2,1), (2,-1), (0,1), (1,2), (1,0), (0,-1), (1,0), (1,-2)\},</math>

which comprises the vertices of a hexagon and its center.

For Minkowski addition, the Template:Em, <math display="inline">\{ 0 \},</math> containing only the zero vector, 0, is an identity element: for every subset S of a vector space,

<math display="block">S + \{0\} = S.</math>

The empty set is important in Minkowski addition, because the empty set annihilates every other subset: for every subset S of a vector space, its sum with the empty set is empty:

<math display="block">S + \emptyset = \emptyset.</math>

For another example, consider the Minkowski sums of open or closed balls in the field <math display="inline">\mathbb{K},</math> which is either the real numbers <math display="inline">\R</math> or complex numbers <math display="inline">\C</math>. If <math display="inline">B_r:= \{ s \in \mathbb{K}: |s| \leq r \}</math> is the closed ball of radius <math display="inline">r \in [0, \infty]</math> centered at <math display="inline">0</math> in <math display="inline">\mathbb{K}</math> then for any <math display="inline">r, s \in [0, \infty]</math>, <math display="inline">B_r + B_s = B_{r+s}</math> and also <math display="inline">c B_r = B_{|c|r}</math> will hold for any scalar <math display="inline">c \in \mathbb{K}</math> such that the product <math display="inline">|c|r</math> is defined (which happens when <math display="inline">c \neq 0</math> or <math display="inline">r \neq \infty</math>). If <math display="inline">r</math>, <math display="inline">s</math>, and <math display="inline">c</math> are all non-zero then the same equalities would still hold had <math display="inline">B_r</math> been defined to be the open ball, rather than the closed ball, centered at 0 (the non-zero assumption is needed because the open ball of radius 0 is the empty set). The Minkowski sum of a closed ball and an open ball is an open ball. More generally, the Minkowski sum of an open subset with Template:Em other set will be an open subset.

If <math display="inline">G = \{ (x, 1/x) : 0 \neq x \in \R \}</math> is the graph of <math display="inline">f(x) = \frac{1}{x}</math> and if and <math display="inline">Y = \{ 0 \} \times \R</math> is the <math display="inline">y</math>-axis in <math display="inline">X = \R^2</math> then the Minkowski sum of these two closed subsets of the plane is the open set <math display="inline">G + Y = \{ (x, y) \in \R^2 : x \neq 0 \} = \R^2 \setminus Y</math> consisting of everything other than the <math display="inline">y</math>-axis. This shows that the Minkowski sum of two closed sets is not necessarily a closed set. However, the Minkowski sum of two closed subsets will be a closed subset if at least one of these sets is also a compact subset.

Convex hulls of Minkowski sumsEdit

Minkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition:

Template:Block indent

This result holds more generally for any finite collection of non-empty sets:

<math display="block">\operatorname{Conv}\left(\sum{S_n}\right) = \sum\operatorname{Conv}(S_n).</math>

In mathematical terminology, the operations of Minkowski summation and of forming convex hulls are commuting operations.<ref>Theorem 3 (pages 562–563): Template:Cite journal</ref><ref>For the commutativity of Minkowski addition and convexification, see Theorem 1.1.2 (pages 2–3) in Schneider; this reference discusses much of the literature on the convex hulls of Minkowski sumsets in its "Chapter 3 Minkowski addition" (pages 126–196): Template:Cite book</ref>

If <math display="inline">S</math> is a convex set then <math>\mu S + \lambda S</math> is also a convex set; furthermore

<math display="block">\mu S + \lambda S = (\mu + \lambda)S</math>

for every <math display="inline">\mu,\lambda \geq 0</math>. Conversely, if this "distributive property" holds for all non-negative real numbers, <math display="inline">\mu</math> and <math display="inline">\lambda</math>, then the set is convex.<ref>Chapter 1: Template:Cite book</ref>

File:Minkowskisum.svg
An example of a non-convex set such that <math display="inline">A + A \neq 2 A.</math>

The figure to the right shows an example of a non-convex set for which <math display="inline">A + A \subsetneq 2 A.</math>

An example in one dimension is: <math display="inline">B = [1, 2] \cup [4, 5].</math> It can be easily calculated that <math display="inline">2 B = [2, 4] \cup [8, 10]</math> but <math display="inline">B + B = [2, 4] \cup [5, 7] \cup [8, 10],</math> hence again <math display="inline">B + B \subsetneq 2 B.</math>

Minkowski sums act linearly on the perimeter of two-dimensional convex bodies: the perimeter of the sum equals the sum of perimeters. Additionally, if <math display="inline">K</math> is (the interior of) a curve of constant width, then the Minkowski sum of <math display="inline">K</math> and of its 180° rotation is a disk. These two facts can be combined to give a short proof of Barbier's theorem on the perimeter of curves of constant width.<ref>The Theorem of Barbier (Java) at cut-the-knot.</ref>

ApplicationsEdit

Minkowski addition plays a central role in mathematical morphology. It arises in the brush-and-stroke paradigm of 2D computer graphics (with various uses, notably by Donald E. Knuth in Metafont), and as the solid sweep operation of 3D computer graphics. It has also been shown to be closely connected to the Earth mover's distance, and by extension, optimal transport.<ref>Template:Cite journal</ref>

Motion planningEdit

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 and rotated 180 degrees.

Numerical control (NC) machiningEdit

In numerical control 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.

3D solid modelingEdit

In OpenSCAD Minkowski sums are used to outline a shape with another shape creating a composite of both shapes.

Aggregation theoryEdit

Minkowski sums are also frequently used in aggregation theory when individual objects to be aggregated are characterized via sets.<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref>

Collision detectionEdit

Minkowski sums, specifically Minkowski differences, are often used alongside GJK algorithms to compute collision detection for convex hulls in physics engines.

Algorithms for computing Minkowski sumsEdit

File:Shapley–Folkman lemma.svg
Minkowski addition and convex hulls. The sixteen dark-red points (on the right) form the Minkowski sum of the four non-convex sets (on the left), each of which consists of a pair of red points. Their convex hulls (shaded pink) contain plus-signs (+): The right plus-sign is the sum of the left plus-signs.

Planar caseEdit

Two convex polygons in the planeEdit

For two convex polygons Template:Var and Template:Var in the plane with Template:Var and Template:Var vertices, their Minkowski sum is a convex polygon with at most Template:Var + Template:Var vertices and may be computed in time O(Template:Var + Template:Var) by a very simple procedure, which may be informally described as follows. Assume that the edges of a polygon are given and 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 Template:Var and Template:Var into a single ordered sequence Template:Var. 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 Template:Var 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 Template:Var and Template:Var.

OtherEdit

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).

Essential Minkowski sumEdit

There is also a notion of the essential Minkowski sum +e of two subsets of Euclidean space. The usual Minkowski sum can be written as

<math display="block">A + B = \left\{ z \in \mathbb{R}^{n} \,|\, A \cap (z - B) \neq \emptyset \right\}.</math>

Thus, the essential Minkowski sum is defined by

<math display="block">A +_{\mathrm{e}} B = \left\{ z \in \mathbb{R}^{n} \,|\, \mu \left[A \cap (z - B)\right] > 0 \right\},</math>

where μ denotes the n-dimensional Lebesgue measure. The reason for the term "essential" is the following property of indicator functions: while

<math display="block">1_{A \,+\, B} (z) = \sup_{x \,\in\, \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),</math>

it can be seen that

<math display="block">1_{A \,+_{\mathrm{e}}\, B} (z) = \mathop{\mathrm{ess\,sup}}_{x \,\in\, \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),</math>

where "ess sup" denotes the essential supremum.

Lp Minkowski sumEdit

For K and L compact convex subsets in <math display="inline">\mathbb{R}^n</math>, the Minkowski sum can be described by the support function of the convex sets:

<math display="block">h_{K+L} = h_K + h_L.</math>

For p ≥ 1, Firey<ref>Template:Citation</ref> defined the Lp Minkowski sum Template:Nowrap of compact convex sets K and L in <math>\mathbb{R}^n</math> containing the origin as

<math display="block">h_{K +_p L}^p = h_K^p + h_L^p.</math>

By the Minkowski inequality, the function hK+pL is again positive homogeneous and convex and hence the support function of a compact convex set. This definition is fundamental in the Lp Brunn-Minkowski theory.

See alsoEdit

NotesEdit

Template:Reflist

ReferencesEdit

External linksEdit

Template:Convex analysis and variational analysis Template:Functional analysis Template:Topological vector spaces

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Minkowski_addition&oldid=310234"