Minkowski Sum of Convex Polygons

For point sets A and B in the plane,

A + B = { a + b | a ∈ A, b ∈ B }

When A and B are convex polygons P and Q (including interiors), the sum P + Q is again a convex polygon with at most |P| + |Q| vertices, and it can be built in linear time.

This lesson follows CP-Algorithms — Minkowski sum.

Related: Basic Geometry (cross products / polar order).

Algorithm

Assume vertices are ordered counter-clockwise and indexed cyclically (P_|P| = P_0, …).

Edge vectors of a convex CCW polygon are already sorted by polar angle once you rotate the listing so the first vertex is the lowest (break ties with leftmost). Merge the two edge sequences by polar angle; when two edges are parallel, replace them by their sum. That merge yields the edges of P + Q.

Working only with summed side vectors can accumulate float error, so the usual implementation builds vertices directly:

1. reorder_polygon so index 0 is lowest (then leftmost).
2. Duplicate P[0], P[1] and Q[0], Q[1] at the end for cyclic access.
3. Pointers i = j = 0. While i < |P| or j < |Q| (accounting for the padding):
   • Append P_i + Q_j to the result.
   • Compare angles of P_iP_{i+1} and Q_jQ_{j+1} via cross (integer-safe).
   • Advance the pointer(s) with the smaller angle (both if equal / parallel).

Distance between two convex polygons

dist(P, Q) = min_{a∈P, b∈Q} ‖a − b‖

Naive checks of vertex–vertex / vertex–edge pairs are O(|P||Q|). With Minkowski sums:

1. Reflect Q through the origin → −Q.
2. Build R = P + (−Q) in O(|P|+|Q|).
3. Distance = distance from 0 to R ( 0 if the origin is inside/on R).

That last query is linear in |R|, so overall O(|P|+|Q|).

Implementation (integer coordinates)

Compare polar angles with the sign of a cross product — no atan2.

struct pt {
    long long x, y;
    pt operator+(const pt& p) const { return {x + p.x, y + p.y}; }
    pt operator-(const pt& p) const { return {x - p.x, y - p.y}; }
    long long cross(const pt& p) const { return x * p.y - y * p.x; }
};

void reorder_polygon(vector<pt>& P) {
    size_t pos = 0;
    for (size_t i = 1; i < P.size(); i++) {
        if (P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
            pos = i;
    }
    rotate(P.begin(), P.begin() + pos, P.end());
}

vector<pt> minkowski(vector<pt> P, vector<pt> Q) {
    reorder_polygon(P);
    reorder_polygon(Q);
    P.push_back(P[0]);
    P.push_back(P[1]);
    Q.push_back(Q[0]);
    Q.push_back(Q[1]);
    vector<pt> result;
    size_t i = 0, j = 0;
    while (i < P.size() - 2 || j < Q.size() - 2) {
        result.push_back(P[i] + Q[j]);
        auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
        if (cross >= 0 && i < P.size() - 2) ++i;
        if (cross <= 0 && j < Q.size() - 2) ++j;
    }
    return result;
}

🧪 Two triangles → pentagon

Check: Minkowski sums

Quiz

Minkowski sum

1 / 4

|P+Q| for convex P,Q is at most…

Pick an answer to see if you are right.

Practice drills

Activity: Point sum

Input: x1 y1 x2 y2. Print x1+x2 and y1+y2.

Contest problems

From CP-Algorithms:

• Codeforces 87E — Mogohu-Rea Idol
• Codeforces 1195F — Geometers Anonymous Club
• TIMUS 1894 — Non-Flying Weather

Cheat sheet

Idea	Takeaway
Sum	{a+b} of convex polygons → convex
Size	≤ |P|+|Q|
Time	O(|P|+|Q|) two-pointer merge
Order	Start at lowest vertex; edges by polar angle
Compare	cross(ΔP, ΔQ) sign
Distance	dist(0, P+(−Q))