Minkowski addition

Last updated
The red figure is the Minkowski sum of blue and green figures. Summa Minkovskogo.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:

Contents

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

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.

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.

The concept is named for Hermann Minkowski.

Example

Minkowski sum A + B Minkowski-sumex4.svg
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 , with coordinates

and

then their Minkowski sum is

which comprises the vertices of a hexagon and its center .

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

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:

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 is the closed ball of radius centered at in then for any and also will hold for any scalar such that the product is defined (which happens when or ). If and are all non-zero then the same equalities would still hold had been defined to be the open ball, rather than the closed ball, centered at (the non-zero assumption is needed because the open ball of radius 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 is the graph of and if and is the -axis in then the Minkowski sum of these two closed subsets of the plane is the open set consisting of everything other than the -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 and of a real vector space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls:

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

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

If is a convex set then is also a convex set; furthermore

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

An example of a non-convex set such that
A
+
A
[?]
2
A
.
{\displaystyle A+A\neq 2A.} Minkowskisum.svg
An example of a non-convex set such that

The figure to the right shows an example of a non-convex set for which

An example in dimension is: It can be easily calculated that but hence again

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

Thus, the essential Minkowski sum is defined by

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

it can be seen that

where "esssup" denotes the essential supremum.

Lp Minkowski sum

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

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

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

Notes

  1. Hadwiger, Hugo (1950), "Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt", Math. Z., 53 (3): 210–218, doi:10.1007/BF01175656, S2CID   121604732 , 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" (PDF). IEEE Transactions on Computers . C-32 (2): 111. doi:10.1109/TC.1983.1676196. hdl:1721.1/5684. S2CID   18978404 . 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. JSTOR   1968735. MR   0002009.
  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. Vol. 44. Cambridge: Cambridge University Press. pp. xiv+490. ISBN   978-0-521-35220-8. MR   1216521.
  6. Chapter 1: Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of mathematics and its applications. Vol. 44. Cambridge: Cambridge University Press. pp. xiv+490. ISBN   978-0-521-35220-8. MR   1216521.
  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 . S2CID   127962240.
  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.
  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.
  11. Firey, William J. (1962), "p-means of convex bodies", Math. Scand., 10: 17–24, doi: 10.7146/math.scand.a-10510

Related Research Articles

In mathematics, more specifically in functional analysis, a Banach space is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vectors and is complete in the sense that a Cauchy sequence of vectors always converges to a well-defined limit that is within the space.

<span class="mw-page-title-main">Convex set</span> In geometry, set whose intersection with every line is a single line segment

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment . For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex.

The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a vector subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear functionals defined on every normed vector space to make the study of the dual space "interesting". Another version of the Hahn–Banach theorem is known as the Hahn–Banach separation theorem or the hyperplane separation theorem, and has numerous uses in convex geometry.

In mathematics, a topological vector space is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is also a topological space with the property that the vector space operations are also continuous functions. Such a topology is called a vector topology and every topological vector space has a uniform topological structure, allowing a notion of uniform convergence and completeness. Some authors also require that the space is a Hausdorff space. One of the most widely studied categories of TVSs are locally convex topological vector spaces. This article focuses on TVSs that are not necessarily locally convex. Banach spaces, Hilbert spaces and Sobolev spaces are other well-known examples of TVSs.

<span class="mw-page-title-main">Minkowski's theorem</span> Every symmetric convex set in R^n with volume > 2^n contains a non-zero integer point

In mathematics, Minkowski's theorem is the statement that every convex set in which is symmetric with respect to the origin and which has volume greater than contains a non-zero integer point. The theorem was proved by Hermann Minkowski in 1889 and became the foundation of the branch of number theory called the geometry of numbers. It can be extended from the integers to any lattice and to any symmetric convex set with volume greater than , where denotes the covolume of the lattice.

In mathematics, a linear form is a linear map from a vector space to its field of scalars.

In vector calculus, Green's theorem relates a line integral around a simple closed curve C to a double integral over the plane region D bounded by C. It is the two-dimensional special case of Stokes' theorem.

<span class="mw-page-title-main">Extreme point</span> Point not between two other points

In mathematics, an extreme point of a convex set in a real or complex vector space is a point in that does not lie in any open line segment joining two points of In linear programming problems, an extreme point is also called vertex or corner point of

In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vector spaces whose topology is generated by translations of balanced, absorbent, convex sets. Alternatively they can be defined as a vector space with a family of seminorms, and a topology can be defined in terms of that family. Although in general such spaces are not necessarily normable, the existence of a convex local base for the zero vector is strong enough for the Hahn–Banach theorem to hold, yielding a sufficiently rich theory of continuous linear functionals.

In geometry, a zonohedron is a convex polyhedron that is centrally symmetric, every face of which is a polygon that is centrally symmetric. Any zonohedron may equivalently be described as the Minkowski sum of a set of line segments in three-dimensional space, or as a three-dimensional projection of a hypercube. Zonohedra were originally defined and studied by E. S. Fedorove, a Russian crystallographer. More generally, in any dimension, the Minkowski sum of line segments forms a polytope known as a zonotope.

In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance in a Euclidean space is defined by a norm on the associated Euclidean vector space, called the Euclidean norm, the 2-norm, or, sometimes, the magnitude of the vector. This norm can be defined as the square root of the inner product of a vector with itself.

In linear algebra, a sublinear function, also called a quasi-seminorm or a Banach functional, on a vector space is a real-valued function with only some of the properties of a seminorm. Unlike seminorms, a sublinear function does not have to be nonnegative-valued and also does not have to be absolutely homogeneous. Seminorms are themselves abstractions of the more well known notion of norms, where a seminorm has all the defining properties of a norm except that it is not required to map non-zero vectors to non-zero values.

In mathematics, Farkas' lemma is a solvability theorem for a finite system of linear inequalities. It was originally proven by the Hungarian mathematician Gyula Farkas. Farkas' lemma is the key result underpinning the linear programming duality and has played a central role in the development of mathematical optimization. It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming. Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of Bell inequalities in the form of necessary and sufficient conditions for the existence of a local hidden-variable theory, given data from any specific set of measurements.

<span class="mw-page-title-main">Krein–Milman theorem</span> On when a space equals the closed convex hull of its extreme points

In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs).

<span class="mw-page-title-main">Star domain</span> Property of point sets in Euclidean spaces

In geometry, a set in the Euclidean space is called a star domain if there exists an such that for all the line segment from to lies in This definition is immediately generalizable to any real, or complex, vector space.

In mathematics, the Brunn–Minkowski theorem is an inequality relating the volumes of compact subsets of Euclidean space. The original version of the Brunn–Minkowski theorem applied to convex sets; the generalization to compact nonconvex sets stated here is due to Lazar Lyusternik (1935).

In mathematics, the relative interior of a set is a refinement of the concept of the interior, which is often more useful when dealing with low-dimensional sets placed in higher-dimensional spaces.

In mathematics, a line integral is an integral where the function to be integrated is evaluated along a curve. The terms path integral, curve integral, and curvilinear integral are also used; contour integral is used as well, although that is typically reserved for line integrals in the complex plane.

<span class="mw-page-title-main">Shapley–Folkman lemma</span> Sums of sets of vectors are nearly convex

The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ross M. Starr.

In mathematics, a matroid polytope, also called a matroid basis polytope to distinguish it from other polytopes derived from a matroid, is a polytope constructed via the bases of a matroid. Given a matroid , the matroid polytope is the convex hull of the indicator vectors of the bases of .

References