x. 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 computed in $O(n+m)$ by merging the two edge sequences by angle.

Property	Value
commutative, associative	$A\oplus B=B\oplus A$
convexity	preserved
vertex count (convex)	$\le n+m$
perimeter	$\mathrm{per}(A)+\mathrm{per}(B)$
area	$\mathrm{area}(A)+\mathrm{area}(B)+2V(A,B)$ (mixed area, Steiner formula)
$A\oplus \{p\}$	translation by $p$
$A\oplus \text{disk}(r)$	offset polygon with rounded corners: perimeter $+2\pi r$, area $+\mathrm{per}(A)r+\pi r^2$
non-convex inputs	complexity up to $O(n^2{m}^2)$; decompose into convex pieces, sum pairwise, take the union (rarely needed)

The construction

1. Rotate each polygon (CCW) so that its bottom-most, then left-most, vertex is first.
2. Merge the two edge sequences by polar angle, as in merge sort (equal angles advance both).
3. Accumulate the edge vectors starting from the sum of the two first 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;
}

Proof: the edges of the sum are the merged edges

For a direction $u$, the support function $h_K(u)={\max }_{k\in K}⟨k,u⟩$ satisfies $h_{A\oplus B}=h_A+h_B$, and the face of $A\oplus B$ maximizing $⟨\cdot ,u⟩$ is the sum of the faces of $A$ and $B$ maximizing it. As $u$ turns around the circle, the maximizing face of a convex polygon is a vertex except at the outer normals of its edges, where it is that edge. So the sum’s edges appear exactly at the edge normals of $A$ and $B$, in angular order, and an edge of the sum is the sum of the edges of $A$ and $B$ with that normal (one of which may be a single vertex). Starting both polygons at their lowest-leftmost vertex aligns the angular starting point, and merging by the cross product of consecutive edges is a merge by angle. Tested against the convex hull of all pairwise vertex sums on random integer polygons.

Uses

Problem	Formulation
collision detection	$A\cap B\ne \varnothing ⟺0\in A\oplus (-B)$ (basis of GJK in physics engines)
distance between convex polygons	distance from the origin to $A\oplus (-B)$
motion planning for a translating robot $R$	grow each obstacle by $\oplus (-R)$, move a point
maximum of $f(a)+g(b)$ over convex sets for linear $f,g$	support function of the sum
reachable set after two moves	sum of the two move sets
max-plus convolution of concave sequences	merge of the slope sequences (below)
widest empty corridor	via Minkowski differences

The collision test is a point-in-convex-polygon query on the Minkowski difference: $O(n+m)$ to build, $O(\log (n+m))$ per query (Convex Polygon Queries).

Proof: the collision criterion

$0\in A\oplus (-B)$ iff there are $a\in A$, $b\in B$ with $a-b=0$, i.e. a common point. The distance version follows the same way: ${\min }_{a,b}|a-b|={\min }_{d\in A\oplus (-B)}|d|$.

Max-plus convolution of concave sequences

For concave $f$ and $g$ (non-increasing differences), $h[k]={\max }_{i+j=k}(f[i]+g[j])$ is obtained by merging the difference sequences in decreasing order, $O(n+m)$ instead of $O(nm)$. This speeds up “combine two convex DP tables” steps (for example in tree knapsack with concave values). Without concavity no subquadratic algorithm is known.

vector<long long> maxPlusConcave(const vector<long long>& f, const vector<long long>& g) {  // f, g concave
    int n = sz(f), m = sz(g); vector<long long> h{f[0] + g[0]};
    int i = 0, j = 0;
    while (i + 1 < n || j + 1 < m) {                 // take the larger next increment (merge of slopes)
        if (j + 1 == m || (i + 1 < n && f[i + 1] - f[i] >= g[j + 1] - g[j])) i++; else j++;
        h.push_back(f[i] + g[j]);
    }
    return h;
}

Proof: merging slopes is optimal

$h[k]-h[0]$ is the maximum sum of $k$ increments chosen as a prefix of $f$‘s differences plus a prefix of $g$‘s differences. Since both difference sequences are non-increasing, the $k$ largest increments of the merged multiset form a prefix of each sequence, and the greedy merge always takes the larger next increment, so after $k$ steps it holds exactly the $k$ largest. This is the one-dimensional case of the Minkowski sum of the hypographs of $f$ and $g$. Tested against the $O(nm)$ definition.

Related: Convex Hull, Rotating Calipers.