TOPICS
Search

Minkowski Sum


The Minkowski sum A+B of two sets A and B in a vector space is given by {a+b:a in A,b in B}.

The Minkowski sum of two disks centered at x_1 and x_2 with radii r_1 and r_2, respectively, is given by the disk centered at x_1+x_2 with radius r_1+r_2. The Minkowski sum of two balls is given similarly.

If A and B are polyhedra, then A+B is a polyhedron and every extreme point of A+B is the sum of an extreme point in A and an extreme point in B.

MinkowskiSumPlatonics

For example, taking the Minkowski sums of the following pairs of Platonic solids in dual position but with unit edge lengths give the following polyhedra.

For semialgebraic sets A,B subset= R^n, membership can be written as

 x in A+B<==> exists a in A exists b in B(x=a+b).

Quantifier elimination removes the existential quantifiers to give a semialgebraic set description of A+B (Trott 2006). If A is a convex body and B is a closed ball centered at the origin, then A+B is a parallel body. For translated sets, (A+u) intersection (B+v)!=⌀ iff v-u in A+(-B), which expresses an intersection test as membership in a Minkowski difference.

The Minkowski sum operation is implemented in the Wolfram Language as RegionDilation.

For compact convex sets, the volume of a scaled Minkowski sum t_1K_1+...+t_nK_n is a polynomial in the nonnegative parameters t_i. Its coefficients define mixed volume (Schneider 2014).


See also

Minkowski Product, Parallel Body, Sum

Explore with Wolfram|Alpha

References

Farouki, R. T.; Moon, H. P.; and Ravani, B. "Minkowski Geometric Algebra of Complex Sets." Geom. Dedicata 85, 283-315, 2001. https://doi.org/10.1023/A:1010318011860.Schneider, R. Convex Bodies: The Brunn-Minkowski Theory, 2nd expanded ed. Cambridge, England: Cambridge University Press, 2014. https://doi.org/10.1017/CBO9781139003858.Skiena, S. S. "Minkowski Sum." §8.6.16 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 395-396, 1997.Trott, M. "Polynomials in Inequalities." §1.2.3 in The Mathematica GuideBook for Symbolics. New York: Springer-Verlag, 2006. https://doi.org/10.1007/0-387-28815-5. https://www.mathematicaguidebooks.org/.

Referenced on Wolfram|Alpha

Minkowski Sum

Cite this as:

Weisstein, Eric W. "Minkowski Sum." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MinkowskiSum.html

Subject classifications