Minkowski addition
Minkowski addition: a short, clear guide
What it is
- If A and B are sets in space, their Minkowski sum A + B is all points you can get by adding a point from A to a point from B. In symbols: A + B = { a + b | a in A, b in B }.
- The sum depends on where the origin is, but its shape is well-defined up to a translation.
Minkowski difference
- The Minkowski difference A − B is the set of all vectors x such that you can add B to x and still stay inside A. It’s defined in a way that makes A = (A − B) + B, so sum and difference are linked symmetrically.
- A simple way to think about it: A − B is the “inverse” operation to A + B, but it’s defined to work with set complements and reflection.
Key ideas to keep in mind
- The sum can fill gaps that the difference might not reopen, and the difference can erase small islands that the sum can’t recreate.
- If you add a set to itself, you get a bigger, smoother shape (often with more pieces if the set is non-convex).
Some basic facts
- Identity and annihilation: S + {0} = S for any S. The empty set annihilates everything: S + ∅ = ∅.
- Balls: If Br is a ball of radius r, then Br + Bs = Br+s and cBr = Br|c| for any scalar c (when the math makes sense). In particular, the sum of two disks is a bigger disk with radius r + s.
- Convex hulls and sums commute: Conv(Σ Sn) = Σ Conv(Sn). In other words, taking convex hulls and taking Minkowski sums can be done in either order.
A simple, visual example
- If you take two convex shapes (like two triangles) in the plane and form their Minkowski sum, you get a new convex shape whose boundary is formed by the “merge” of their edges.
What happens with non-convex shapes
- For non-convex shapes, the Minkowski sum can be more complex, and sometimes it can add new parts that weren’t in either shape alone.
Perimeter and constant-width shapes (a hint of geometry)
- For many 2D convex bodies, the perimeter behaves nicely: the perimeter of the sum is the sum of the perimeters.
- If you sum a shape with its 180-degree rotation (for a constant-width shape), you can get a disk. This idea is related to Barbier’s theorem about perimeters.
Where it’s used
- In computer graphics and image processing: dilation (sum) and erosion (difference) help shape and analyze images.
- In robotics and motion planning: the configuration space (all possible positions) can be found using Minkowski sums to account for obstacles.
- In manufacturing and design: tools and paths are planned by combining shapes to see the resulting cut or sweep.
- In math and computation: Minkowski sums help study convexity, support functions, and related geometric properties.
How to compute it for polygons
- For two convex polygons with m and n vertices, the Minkowski sum is a convex polygon with at most m + n vertices, and you can compute it in O(m + n) time by merging their edge directions in order.
Variants worth knowing
- Essential Minkowski sum: a version that focuses on where the intersection has positive area, using measure theory (Lebesgue measure) to avoid some degenerate cases.
- Open and closed sums: different types of balls (open vs. closed) behave in predictable ways under Minkowski addition, which matters for open/closed sets and their interiors.
- Support function view: for convex sets, the Minkowski sum corresponds to adding their support functions, so h_{A+B} = h_A + h_B.
- Lp Minkowski sum: a generalization that uses a parameter p and the corresponding Lp support functions, important in advanced geometry and the Lp Brunn–Minkowski theory.
In short
- Minkowski addition is a simple rule: add every point of A to every point of B and collect the results.
- It has neat algebraic and geometric properties, with wide applications from graphics to planning and analysis.
- There are useful variants and efficient ways to compute it, especially for convex shapes.
This page was last edited on 2 February 2026, at 06:01 (CET).