Minkowski addition

Short description: Sums vector sets A and B by adding each vector in A to each vector in B

The red figure is the Minkowski sum of blue and green figures.

In mathematics, the sumset of two subsets A and B of an (additive) abelian group is formed by adding each element of A to each element of B: A+B={a+b∣a∈A, b∈B}.

In geometry, the Minkowski sum of two subsets A and B of a Euclidean space is the set of the points whose position vectors form the sumset of the position vectors of A and B. The Minkowski sum depends on the choice of an origin in the Euclidean space. As a change of origin amounts to translate the Minkowski sum, the Minkowski sum is defined up to a translation, and its shape and orientation are well defined.

The Minkowski difference (also Minkowski subtraction, Minkowski decomposition, or geometric difference)[1] is the corresponding inverse, where (A−B) 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.[2]

−B={−𝐛|𝐛∈B}A−B=(A∁+(−B))∁

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.

(A−B)+B⊆A(A+B)−B⊇AA−B=(A∁+(−B))∁A+B=(A∁−(−B))∁

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.[3] 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.

A−B={𝐚−𝐛|𝐚∈A, 𝐛∈B}=A+(−B)

The concept is named for Hermann Minkowski.

## Contents

* 1 Example
* 2 Convex hulls of Minkowski sums
* 3 Applications
* 3.1 Motion planning
* 3.2 Numerical control (NC) machining
* 3.3 3D solid modeling
* 3.4 Aggregation theory
* 3.5 Collision detection
* 4 Algorithms for computing Minkowski sums
* 4.1 Planar case
* 4.1.1 Two convex polygons in the plane
* 4.1.2 Other
* 5 Essential Minkowski sum
* 6 Lp Minkowski sum
* 7 See also
* 8 Notes
* 9 References
* 10 External links

## Example

Minkowski sum A \+ B

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 ℝ2, with coordinates

A={(1,0),(0,1),(0,−1)}

and

B={(0,0),(1,1),(1,−1)}

then their Minkowski sum is

A+B={(1,0),(2,1),(2,−1),(0,1),(1,2),(1,0),(0,−1),(1,0),(1,−2)},

which comprises the vertices of a hexagon and its center.

For Minkowski addition, the zero set, {0}, containing only the zero vector, 0, is an identity element: for every subset S of a vector space,

S+{0}=S.

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:

S+∅=∅.

For another example, consider the Minkowski sums of open or closed balls in the field 𝕂, which is either the real numbers ℝ or complex numbers ℂ. If Br:={s∈𝕂:|s|≤r} is the closed ball of radius r∈[0,∞] centered at 0 in 𝕂 then for any r,s∈[0,∞], Br+Bs=Br+s and also cBr=B|c|r will hold for any scalar c∈𝕂 such that the product |c|r is defined (which happens when c≠0 or r≠∞). If r, s, and c are all non-zero then the same equalities would still hold had Br 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 any other set will be an open subset.

If G={(x,1/x):0≠x∈ℝ} is the graph of f(x)=1x and if and Y={0}×ℝ is the y-axis in X=ℝ2 then the Minkowski sum of these two closed subsets of the plane is the open set G+Y={(x,y)∈ℝ2:x≠0}=ℝ2∖Y consisting of everything other than the y-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 sums

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

For all non-empty subsets S1 and S2 of a real vector space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls: Conv⁡(S1+S2)=Conv⁡(S1)+Conv⁡(S2).

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

Conv⁡(∑Sn)=∑Conv⁡(Sn).

In mathematical terminology, the operations of Minkowski summation and of forming convex hulls are commuting operations.[4][5]

If S is a convex set then μS+λS is also a convex set; furthermore

μS+λS=(μ+λ)S

for every μ,λ≥0. Conversely, if this "distributive property" holds for all non-negative real numbers, μ and λ, then the set is convex.[6]

An example of a non-convex set such that A+A≠2A.

The figure to the right shows an example of a non-convex set for which 2A⊊A+A.

An example in one dimension is: B=[1,2]∪[4,5]. It can be easily calculated that 2B=[2,4]∪[8,10] but B+B=[2,4]∪[5,7]∪[8,10], hence again 2B⊊B+B.

Minkowski sums act linearly on the perimeter of two-dimensional convex bodies: the perimeter of the sum equals the sum of perimeters. Additionally, if K is (the interior of) a curve of constant width, then the Minkowski sum of K 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.[7]

## Applications

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.[8]

### Motion planning

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

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 modeling

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

### Aggregation theory

Minkowski sums are also frequently used in aggregation theory when individual objects to be aggregated are characterized via sets.[9][10]

### Collision detection

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 sums

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 case

#### Two convex polygons in the plane

For two convex polygons P and Q in the plane with m and n vertices, their Minkowski sum is a convex polygon with at most m \+ n vertices and may be computed in time O(m \+ n) 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 P and Q into a single ordered sequence S. 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 S 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 P and Q.

#### Other

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 sum

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

A+B={z∈ℝn|A∩(z−B)≠∅}.

Thus, the essential Minkowski sum is defined by

A+eB={z∈ℝn|μ[A∩(z−B)]>0},

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

1A+B(z)=supx∈ℝn1A(x)1B(z−x),

it can be seen that

1A+eB(z)=esssupx∈ℝn1A(x)1B(z−x),

where "ess sup" denotes the essential supremum.

## Lp Minkowski sum

For K and L compact convex subsets in ℝn, the Minkowski sum can be described by the support function of the convex sets:

hK+L=hK+hL.

For p ≥ 1, Firey[11] defined the Lp Minkowski sum K +p L of compact convex sets K and L in ℝn containing the origin as

hK+pLp=hKp+hLp.

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 also

* Blaschke sum - Polytope combining two smaller polytopes
* Brunn–Minkowski theorem - Theorem in geometry, an inequality on the volumes of Minkowski sums
* Convolution
* Dilation - Operation in mathematical morphology
* Erosion - Basic operation in mathematical morphology
* Interval arithmetic - Method for bounding the errors of numerical computations
* Mixed volume (a.k.a. Quermassintegral or intrinsic volume)
* Parallel curve - Generalization of the concept of parallel lines
* Shapley–Folkman lemma - Sums of sets of vectors are nearly convex

## Notes

1. ↑ Hadwiger, Hugo (1950), [214} "Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt"], Mathematische Zeitschrift 53 (3): 210–218, doi:10.1007/BF01175656, https://gdz.sub.uni-goettingen.de/id/PPN266833020_0053?tify={"pages":[214]}, retrieved 2023-01-12
2. ↑ Li, Wei (Fall 2011). GPU-Based Computation of Voxelized Minkowski Sums with Applications (PhD). UC Berkeley. pp. 13–14. Retrieved 2023-01-10.
3. ↑ Lozano-Pérez, Tomás (February 1983). "Spatial Planning: A Configuration Space Approach". IEEE Transactions on Computers C-32 (2): 111. doi:10.1109/TC.1983.1676196. https://lis.csail.mit.edu/pubs/tlp/spatial-planning.pdf. Retrieved 2023-01-10.
4. ↑ Theorem 3 (pages 562–563): Krein, M.; Šmulian, V. (1940). "On regularly convex sets in the space conjugate to a Banach space". Annals of Mathematics. Second Series 41 (3): 556–583. doi:10.2307/1968735.
5. ↑ 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): Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of mathematics and its applications. 44. Cambridge: Cambridge University Press. pp. xiv+490. ISBN 978-0-521-35220-8. https://archive.org/details/convexbodiesbrun0000schn.
6. ↑ Chapter 1: Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of mathematics and its applications. 44. Cambridge: Cambridge University Press. pp. xiv+490. ISBN 978-0-521-35220-8. https://archive.org/details/convexbodiesbrun0000schn.
7. ↑ The Theorem of Barbier (Java) at cut-the-knot.
8. ↑ Kline, Jeffery (2019). "Properties of the d-dimensional earth mover's problem". Discrete Applied Mathematics 265: 128–141. doi:10.1016/j.dam.2019.02.042.
9. ↑ Zelenyuk, V. (2015). "Aggregation of scale efficiency". European Journal of Operational Research 240 (1): 269–277. doi:10.1016/j.ejor.2014.06.038. https://ideas.repec.org/a/eee/ejores/v240y2015i1p269-277.html.
10. ↑ Mayer, A.; Zelenyuk, V. (2014). "Aggregation of Malmquist productivity indexes allowing for reallocation of resources". European Journal of Operational Research 238 (3): 774–785. doi:10.1016/j.ejor.2014.04.003. https://ideas.repec.org/a/eee/ejores/v238y2014i3p774-785.html.
11. ↑ Firey, William J. (1962), "p-means of convex bodies", Mathematica Scandinavica 10: 17–24, doi:10.7146/math.scand.a-10510

## References

* Arrow, Kenneth J.; Hahn, Frank H. (1980). General competitive analysis. Advanced textbooks in economics. 12 (reprint of (1971) San Francisco, CA: Holden-Day, Inc. Mathematical economics texts. 6 ed.). Amsterdam: North-Holland. ISBN 978-0-444-85497-1.
* Gardner, Richard J. (2002), "The Brunn-Minkowski inequality", Bull. Amer. Math. Soc. (N.S.) 39 (3): 355–405 (electronic), doi:10.1090/S0273-0979-02-00941-2
* Green, Jerry; Heller, Walter P. (1981). "1 Mathematical analysis and convexity with applications to economics". in Arrow, Kenneth Joseph; Intriligator, Michael D. Handbook of mathematical economics, Volume I. Handbooks in economics. 1. Amsterdam: North-Holland Publishing Co. pp. 15–52. doi:10.1016/S1573-4382(81)01005-9. ISBN 978-0-444-86126-9.
* Addition Theorems: The Addition Theorems of Group Theory and Number Theory (Corrected reprint of 1965 Wiley ed.), Huntington, New York: Robert E. Krieger Publishing Company, 1976, ISBN 978-0-88275-418-5
* Rockafellar, R. Tyrrell (1997). Convex analysis. Princeton landmarks in mathematics (Reprint of the 1979 Princeton mathematical series 28 ed.). Princeton, NJ: Princeton University Press. pp. xviii+451. ISBN 978-0-691-01586-6.
* Nathanson, Melvyn B. (1996), Additive Number Theory: Inverse Problems and Geometry of Sumsets, GTM, 165, Springer .
* Oks, Eduard; Sharir, Micha (2006), "Minkowski Sums of Monotone and General Simple Polygons", Discrete & Computational Geometry 35 (2): 223–240, doi:10.1007/s00454-005-1206-y .
* Schneider, Rolf (1993), Convex bodies: the Brunn-Minkowski theory, Cambridge: Cambridge University Press .
* Tao, Terence; Vu, Van (2006), Additive Combinatorics, Cambridge University Press .
* Mayer, A.; Zelenyuk, V. (2014). "Aggregation of Malmquist productivity indexes allowing for reallocation of resources". European Journal of Operational Research 238 (3): 774–785. doi:10.1016/j.ejor.2014.04.003. https://ideas.repec.org/a/eee/ejores/v238y2014i3p774-785.html.
* Zelenyuk, V (2015). "Aggregation of scale efficiency". European Journal of Operational Research 240 (1): 269–277. doi:10.1016/j.ejor.2014.06.038. https://ideas.repec.org/a/eee/ejores/v240y2015i1p269-277.html.

## External links

* Hazewinkel, Michiel, ed. (2001), "Minkowski addition", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=p/m120210
* Howe, Roger (1979), On the tendency toward convexity of the vector sum of sets, Cowles Foundation discussion papers, 538, Cowles Foundation for Research in Economics, Yale University, http://econpapers.repec.org/RePEc:cwl:cwldpp:538
* Minkowski Sums, in Computational Geometry Algorithms Library
* The Minkowski Sum of Two Triangles and The Minkowski Sum of a Disk and a Polygon by George Beck, The Wolfram Demonstrations Project.
* Minkowski's addition of convex shapes by Alexander Bogomolny: an applet
* Wikibooks:OpenSCAD User Manual/Transformations#minkowski by Marius Kintel: Application
* Application of Minkowski Addition to robotics by Joan Gerard
* Demonstration of Minkowski additivity, convex monotonicity, and other properties of the Earth Movers distance

Template:Convex analysis and variational analysis

* v
* t
* e

Functional analysis (topics)

Topological vector spaces|

* Asplund
* Banach (list)
* Banach lattice
* Barrelled
* Bornological
* Brauner
* F-space
* Fréchet (tame)
* Hilbert (Inner product space
* Polarization identity)
* LF-space
* Locally convex (Seminorms/Minkowski functionals)
* Mackey
* Montel
* Nuclear
* Normed (norm)
* Quasinormed
* Reflexive
* Riesz
* Smith
* Stereotype
* Strictly convex
* Webbed
* Topological tensor product (of Hilbert spaces)

Topologies of function spaces|

* Dual
* Dual space (Dual norm)
* Operator
* Ultraweak
* Weak (polar
* operator)
* Mackey
* Strong (polar
* operator)
* Ultrastrong
* Uniform convergence

Linear operators|

* Adjoint
* Bilinear (form
* operator
* sesquilinear)
* (Un)Bounded
* Closed
* Compact (on Hilbert spaces)
* (Dis)Continuous
* Densely defined
* Fredholm
* Hilbert–Schmidt
* Functionals (positive)
* Normal
* Nuclear
* Self-adjoint
* Strictly singular
* Trace class
* Transpose
* Unitary

Operator theory|

* Banach algebras
* C*-algebras
* Spectrum (C*-algebra
* radius)
* Spectral theory (of ODEs
* Spectral theorem)
* Polar decomposition
* Singular value decomposition

Theorems|

* Banach–Alaoglu
* Banach–Mazur
* Banach–Saks
* Banach–Schauder (open mapping)
* Banach–Steinhaus (Uniform boundedness)
* Bessel's inequality
* Cauchy–Schwarz inequality
* Closed graph
* Closed range
* Eberlein–Šmulian
* Freudenthal spectral
* Gelfand–Mazur
* Gelfand–Naimark
* Goldstine
* Hahn–Banach (hyperplane separation)
* Kakutani fixed-point
* Krein–Milman
* Lomonosov's invariant subspace
* Mackey–Arens
* Mazur's lemma
* M. Riesz extension
* Riesz representation
* Parseval's identity
* Schauder fixed-point

Analysis|

* Abstract Wiener space
* Bochner space
* Differentiation in Fréchet spaces
* Derivatives (Fréchet
* Gateaux
* functional
* holomorphic)
* Integrals (Bochner
* Dunford
* Gelfand–Pettis
* regulated
* Paley–Wiener
* weak)
* Functional calculus (Borel
* continuous
* holomorphic)
* Inverse function theorem (Nash–Moser theorem)
* Measures (Lebesgue
* Projection-valued
* Vector)
* Weakly measurable function

Types of sets|

* Absolutely convex
* Absorbing
* Balanced
* Bounded
* Convex
* Convex cone (subset)
* Linear cone (subset)
* Radial
* Star-shaped
* Symmetric
* Zonotope

Subsets / set operations|

* Algebraic interior (core)
* Bounding points
* Convex hull
* Extreme point
* Interior
* Minkowski addition
* Polar

Template:Topological vector spaces

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Minkowski addition. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Minkowski_addition&oldid=3980656"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template