Minkowski Sum

$A\oplus B=\{a+b:a\in A,b\in B\}.$

For convex polygons the sum is convex, has at most $n+m$ vertices, and is computable in $O(n+m)$.

The construction

The edges of $A\oplus B$ are exactly the edges of $A$ and $B$, merged by angle. So:

1. Rotate each polygon so its bottom-most (then left-most) vertex is first.
2. Merge the two edge sequences by angle, as in a merge sort.
3. Accumulate the edge vectors from the sum of the two starting vertices.

vector<P> minkowski(vector<P> a, vector<P> b) {       // both CCW, both starting at the lowest point
    a.push_back(a[0]); a.push_back(a[1]);
    b.push_back(b[0]); b.push_back(b[1]);
    vector<P> res;
    size_t i = 0, j = 0;
    while (i + 2 < a.size() || j + 2 < b.size()) {
        res.push_back(a[i] + b[j]);
        long long c = cross(a[i+1] - a[i], b[j+1] - b[j]);
        if (c >= 0 && i + 2 < a.size()) i++;
        if (c <= 0 && j + 2 < b.size()) j++;
    }
    return res;
}

$O(n+m)$ — one pass, exact in integers.

Why the edges just merge

A convex polygon is determined by its multiset of edge vectors sorted by angle. Supporting the sum in a direction $\hat{u}$ means supporting $A$ and $B$ separately in $\hat{u}$, so the sum’s edge in each angular direction is the sum of the two polygons’ edges in that direction. Merging by angle is therefore the whole algorithm.

Uses

Problem	Formulation
Collision detection	$A$ and $B$ intersect iff $0\in A\oplus (-B)$
Distance between convex polygons	distance from the origin to $A\oplus (-B)$
Motion planning with a robot of shape $R$	grow every obstacle by $\oplus (-R)$, then treat the robot as a point
Maximum of $f(a)+g(b)$ over convex sets	support function of the sum
Sum of two convex sequences (max-plus convolution)	the sequences are the edge slopes
Reachable set after two moves	$\oplus$ of the two move sets
Widest empty corridor	via Minkowski differences

The collision test

$A\cap B\ne \varnothing ⟺0\in A\oplus (-B).$

Since $A\oplus (-B)$ (the Minkowski difference) is convex and computable in $O(n+m)$, the test is a point-in-convex-polygon query — $O(\log (n+m))$ after construction. This is the theoretical basis of the GJK algorithm used in every physics engine.

Max-plus convolution of concave sequences

If $f$ and $g$ are concave, then

$(f\oplus g)[k]={\max }_{i+j=k}(f[i]+g[j])$

is computable in $O(n+m)$ by merging their difference sequences — because the problem is a Minkowski sum of the two convex hulls of their graphs. Without concavity, max-plus convolution has no known subquadratic algorithm.

This turns certain “combine two convex DP tables” problems from $O(nm)$ into $O(n+m)$, and it is a genuinely useful trick in optimisation-flavoured DPs.

Properties

Property
Commutative and associative	$A\oplus B=B\oplus A$
Convexity is preserved	sum of convex sets is convex
Vertex count	$\le n+m$
Perimeter	$\mathrm{per}(A)+\mathrm{per}(B)$
Area (Steiner formula)	$\mathrm{area}(A)+\mathrm{area}(B)+\text{mixed area}$
$A\oplus \{p\}$	translation of $A$ by $p$
$A\oplus \text{disk}(r)$	$A$ “inflated” by $r$ — rounded corners

Inflating a polygon by a disk gives the offset polygon with rounded corners: straight edges pushed out by $r$, joined by arcs of radius $r$. Perimeter grows by exactly $2\pi r$, area by $\mathrm{per}(A)\cdot r+\pi r^2$.

Non-convex inputs

For non-convex polygons the Minkowski sum can have $O(n^2{m}^2)$ complexity and requires arrangement machinery to compute. In practice: decompose into convex pieces, sum pairwise, and take the union — expensive, and rarely needed in contests.

See also: Convex Hull · Rotating Calipers · Convex Hull Trick