Editing Minkowski addition (section)

{{short description|Sums vector sets A and B by adding each vector in A to each vector in B}}
[[File:Сумма Минковского.svg|thumb|alt=|The red figure is the Minkowski sum of blue and green figures.]]

In [[geometry]], the '''Minkowski sum''' of two [[set (mathematics)|sets]] of [[position vector]]s ''A'' and ''B'' in [[Euclidean space]] is formed by [[vector addition|adding each vector]] in ''A'' to each vector in ''B'':

<math display="block">A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}</math>

The '''Minkowski difference''' (also ''Minkowski subtraction'', ''Minkowski decomposition'', or ''geometric difference'')<ref>{{citation |last=Hadwiger |first=Hugo|title=Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt |journal=Mathematische Zeitschrift |volume=53 |issue=3 |pages=210–218 |year=1950 |doi=10.1007/BF01175656 |s2cid=121604732 |url=https://gdz.sub.uni-goettingen.de/id/PPN266833020_0053?tify={%22pages%22:[214]} |access-date=2023-01-12}}</ref> is the corresponding inverse, where <math display="inline">(A - B)</math> produces a set that could be summed with ''B'' to recover ''A''. This is defined as the [[Complement (set theory)|complement]] of the Minkowski sum of the complement of ''A'' with the reflection of ''B'' about the origin.<ref>{{cite thesis |last=Li |first=Wei |date=Fall 2011 |title=GPU-Based Computation of Voxelized Minkowski Sums with Applications |url=https://escholarship.org/uc/item/9rm7j1pq |type=PhD |publisher=[[UC Berkeley]] |pages=13–14 |access-date=2023-01-10}}</ref>

<math display="block">\begin{align}
-B &= \{\mathbf{-b}\,|\,\mathbf{b}\in B\}\\
A - B &= (A^\complement + (-B))^\complement
\end{align}</math>

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.

<math display="block">\begin{align}
(A - B) + B &\subseteq A\\
(A + B) - B &\supseteq A\\
A - B &= (A^\complement + (-B))^\complement\\
A + B &= (A^\complement - (-B))^\complement\\
\end{align}</math>

In 2D [[image processing]] the Minkowski sum and difference are known as [[Dilation (morphology)|dilation]] and [[Erosion (morphology)|erosion]].

An alternative definition of the Minkowski difference is sometimes used for computing intersection of convex shapes.<ref>{{cite journal |last=Lozano-Pérez |first=Tomás |date=February 1983 |title=Spatial Planning: A Configuration Space Approach |url=https://lis.csail.mit.edu/pubs/tlp/spatial-planning.pdf |journal=[[IEEE Transactions on Computers]] |volume=C-32 |issue=2 |pages=111 |doi=10.1109/TC.1983.1676196 |hdl=1721.1/5684 |s2cid=18978404 |access-date=2023-01-10}}</ref> 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.

<math display="block">A - B = \{\mathbf{a}-\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\} = A + (-B)</math>

The concept is named for [[Hermann Minkowski]].