Minkowski addition
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.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.If the two convex shapes intersect, the resulting set will contain the origin.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 inFor another example, consider the Minkowski sums of open or closed balls in the fieldthen the Minkowski sum of these two closed subsets of the plane is the open setMinkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition: This result holds more generally for any finite collection of non-empty sets:Conversely, if this "distributive property" holds for all non-negative real numbers,is (the interior of) a curve of constant width, then the Minkowski sum ofThese two facts can be combined to give a short proof of Barbier's theorem on the perimeter of curves of constant width.[7] 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] 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 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.[9][10] Minkowski sums, specifically Minkowski differences, are often used alongside GJK algorithms to compute collision detection for convex hulls in physics engines.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.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.If one polygon is convex and another one is not, the complexity of their Minkowski sum is O(nm).There is also a notion of the essential Minkowski sum +e of two subsets of Euclidean space.where μ denotes the n-dimensional Lebesgue measure.The reason for the term "essential" is the following property of indicator functions: while, the Minkowski sum can be described by the support function of the convex sets:For p ≥ 1, Firey[11] defined the Lp Minkowski sum K +p L of compact convex sets K and L inThis definition is fundamental in the Lp Brunn-Minkowski theory.
geometryposition vectorsEuclidean spaceadding each vectorcomplementimage processingdilationerosionvector subtractionHermann Minkowskiverticestriangleszero vectoridentity elementempty setreal numberscomplex numbersopen subsetclosed subsetsopen setclosed setscompact subsetconvex hullsoperationscommutingdistributive propertycurve of constant widthBarbier's theoremmathematical morphology2D computer graphicsDonald E. KnuthMetafontsolid sweep3D computer graphicsEarth mover's distanceoptimal transportmotion planningconfiguration spacenumerical controlOpenSCADGJK algorithmscollision detectionphysics enginesconvex polygonspolar anglemerge the ordered sequencesarrowspolygonal chainLebesgue measureindicator functionsessential supremumsupport functionMinkowski inequalityBlaschke sumBrunn–Minkowski theoremConvolutionInterval arithmeticMixed volumeQuermassintegralParallel curveShapley–Folkman lemmaSumsetZonotopeUC BerkeleyIEEE Transactions on ComputersKrein, M.convexificationsumsetscut-the-knotArrow, Kenneth J.Hahn, Frank H.Arrow, Kenneth JosephHenry MannRockafellar, R. TyrrellSharir, MichaDiscrete & Computational GeometryEncyclopedia of MathematicsEMS PressHowe, RogerCowles Foundation for Research in EconomicsComputational Geometry Algorithms LibraryThe Wolfram Demonstrations ProjectAlexander BogomolnyConvex analysisvariational analysisConvex combinationConvex functionConvex setTopics (list)Choquet theoryConvex geometryConvex metric spaceConvex optimizationDualityLagrange multiplierLegendre transformationLocally convex topological vector spaceSimplexConvex conjugateConcaveClosedLogarithmicallyProperPseudo-Quasi-Invex functionSemi-continuitySubderivativeCarathéodory's theoremEkeland's variational principleFenchel–Moreau theoremFenchel-Young inequalityJensen's inequalityHermite–Hadamard inequalityKrein–Milman theoremMazur's lemmaUrsescuConvex hullOrthogonallyEffective domainEpigraphHypographJohn ellipsoidRadial setAlgebraic interiorDual system