This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000504105 Reproduction Date:
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
Analogously, the Minkowski difference is defined as
The concept is named for Hermann Minkowski.
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
and
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
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 + \emptyset = \emptyset.
Minkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition:
This result holds more generally for each finite collection of non-empty sets
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
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 ⊋ 2A.
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 ⊋ 2B.
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]}
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.
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.
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.
In OpenSCAD Minkowski sums are used to outline a shape with another shape creating a composite of both shapes.
Minkowski sums are also frequently used in aggregation theory when individual objects to be aggregated are characterized via sets.^{[4]}^{[5]}
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.
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}).
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
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 "ess sup" denotes the essential supremum.
Topology, Calculus, Euclid, Projective geometry, Algebraic geometry
Statistics, Game theory, Mathematics, Set theory, Convex set
Animation, 3D rendering, 3D printing, Computer animation, 3D modeling
Linear algebra, Banach space, Integral, Hilbert space, Game theory
Game theory, Infinity, Probability theory, Microeconomics, Convex set
Functional analysis, Convex hull, Euclidean space, Minkowski addition, Sumset
Cube, Hexagonal prism, Truncated octahedron, Rhombic dodecahedron, MathWorld