Minkowski addition

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

In geometry, the Minkowski sum (also known as dilation) 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, i.e., the set

A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}.

Analogously, the Minkowski difference is defined as

A - B = \{\mathbf{a}-\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}.

Minkowski sum

A + B

The concept is named for Hermann Minkowski.

Example

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 $\mathbb{R}^2$ , with coordinates

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

and

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

then the Minkowski sum is
$A + B =$ { $(1, 0)$ , $(2, 1)$ , $(2, -1)$ , $(0, 1)$ , $(1, 2)$ , $(1, 0)$ , $(0, -1)$ , $(1, 0)$ , $(1, -2)$ }, which looks like a hexagon, with three 'repeated' points at $(1, 0)$ .

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: $\emptyset$ .

A picture of a smoothed triangle, like a triangular tortilla-chip or a triangular road-sign. Each of the three rounded corners is drawn with a red curve. The remaining interior points of the triangular shape are shaded with blue.

In the convex hull of the red set, each blue point is a convex combination of some red points.

Three squares are shown in the non-negative quadrant of the Cartesian plane. The square Q1=[0,1]×[0,1] is green. The square Q2=[1,2]×[1,2] is brown, and it sits inside the turquoise square Q1+Q2=[1,3]×[1,3].

Minkowski addition of sets. The sum of the squares Q₁=

[0,1]

² and Q₂=

[1,2]

² is the square Q₁+Q₂=

[1,3]

².

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 S₁ and S₂ of a real vector-space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls

Conv(S₁ + S₂) = Conv(S₁) + Conv(S₂).

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

Conv(∑S_n) = ∑Conv(S_n).

In mathematical terminology, the operations of Minkowski summation and of forming convex hulls are commuting operations.^[1]^[2]

If $S$ is a convex set then also $\mu S+\lambda S$ is a convex set; furthermore

\mu S+\lambda S=(\mu+\lambda)S

for every

\mu,\lambda \geq 0

Conversely, if this "distributive property" holds for all non-negative real numbers, $\mu, \lambda$ , then the set is convex.^[2]

The figure shows an example of a non-convex set for which $A + A ⊋ 2 A$ .

An example of a non-convex set such that

A + A \neq 2 A

An example in 1 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 $B + B ⊋ 2 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.^[3]

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.

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.^[4]^[5]

Algorithms for computing Minkowski sums

Minkowski addition of four line-segments. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line-segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus-symbol. In the top row of the two-by-two array, the plus-symbol lies in the interior of the line segment; in the bottom row, the plus-symbol coincides with one of the red-points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand-set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum-points are the sums of the left-hand red summand-points. The convex hull of the sixteen red-points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. The right-hand plus-symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand-sets and two points from the convex hulls of the remaining summand-sets.

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

Essential Minkowski sum

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

A + B = \{ z \in \mathbb{R}^{n} \,|\, A \cap (\{z\} - B) \neq \emptyset \}.

Thus, the essential Minkowski sum is defined by

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

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

1_{A \,+\, B} (z) = \sup_{x \,\in\, \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),

it can be seen that

1_{A \,+_{\mathrm{e}}\, B} (z) = \mathop{\mathrm{ess\,sup}}_{x \,\in\, \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),

where "ess sup" denotes the essential supremum.

Notes

↑ 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 (2), Second series 41. pp. 556–583. doi:10.2307/1968735. JSTOR 1968735. MR 2009.
1 2 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 0-521-35220-7. MR 1216521.
↑ The Theorem of Barbier (Java) at cut-the-knot.
↑ Zelenyuk, V. (2015) "Aggregation of scale efficiency," European Journal of Operational Research, 240:1, pp 269-277.
↑ Mayer, A. and Zelenyuk, V. (2014) "Aggregation of Malmquist productivity indexes allowing for reallocation of resources," European Journal of Operational Research, 238:3, pp 774-785

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 0-444-85497-5. MR 439057.
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 0-444-86126-2. MR 634800.
Henry Mann (1976), 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, ISBN 0-88275-418-1 External link in |publisher= (help)
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 0-691-01586-4. MR 1451876. MR 274683.
Nathanson, Melvyn B. (1996), Additive Number Theory: Inverse Problems and Geometry of Sumsets, GTM 165, Springer, Zbl 0859.11003 .
Oks, Eduard; Sharir, Micha (2006), "Minkowski Sums of Monotone and General Simple Polygons", Discrete and 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. and Zelenyuk, V. (2014) "Aggregation of Malmquist productivity indexes allowing for reallocation of resources," European Journal of Operational Research, 238:3, pp 774-785
Zelenyuk, V. (2015) "Aggregation of scale efficiency," European Journal of Operational Research, 240:1, pp 269-277.

External links

Hazewinkel, Michiel, ed. (2001), "Minkowski addition", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
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
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

Functional analysis

Set / subset types	Absolutely convex Absorbing Balanced Bounded Convex Radial Star-shaped Symmetric Linear cone (subset) Convex cone (subset)

TVS types	Banach Barrelled Bornological Brauner F-space Finite-dimensional Fréchet (tame) Hilbert LF-space Locally convex Mackey Montel Nuclear Normed (norm) Quasinormed Reflexive Riesz Smith Stereotype Webbed Topological tensor product (of Hilbert spaces)

Mapping topologies	Dual Dual space Operator Strong (polar operator) Ultrastrong Weak (operator) Ultraweak Uniform convergence

Linear operators	Adjoint Bilinear (form) Bounded / Unbounded Closed Continuous / Discontinuous Compact Fredholm Hilbert–Schmidt Functionals (positive) Normal Nuclear Self-adjoint Strictly singular Trace class Transpose Unitary

Set operations	Algebraic interior (core) Interior Minkowski addition Polar

Banach algebras	C-algebras Spectrum (C-algebra radius) Spectral theory

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

Analysis	Bochner space Differentiation in Fréchet spaces Derivatives (Fréchet Gâteaux functional holomorphic) Integrals (Bochner Dunford Gelfand–Pettis regulated weak) Functional calculus (Borel continuous holomorphic) Inverse function theorem (Nash–Moser theorem) Vector measure

This article is issued from Wikipedia - version of the Monday, March 14, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.