⚙️AlgorithmAdvanced

Minkowski Sum

Key Points

  • •
    The Minkowski sum A ⊕ B adds every point of set A to every point of set B, and for convex polygons it can be computed in O(n + m) by merging edge directions.
  • •
    To run the linear algorithm, start both polygons at their lowest-leftmost vertex, ensure counterclockwise order, and merge edge vectors by increasing polar angle.
  • •
    Collision detection between two convex shapes reduces to testing whether the origin lies inside A ⊕ (−B).
  • •
    The support function of a Minkowski sum is the sum of supports: (u) = (u) + (u), which explains the angle-merge algorithm.
  • •
    For general point sets, the convex hull of pairwise sums equals the Minkowski sum of the convex hulls: conv(A + B) = conv(A) ⊕ conv(B).
  • •
    Numerical robustness matters: normalize polygon orientation, remove collinear duplicates, and be careful with floating-point epsilons.
  • •
    The Minkowski sum is convex if both inputs are convex, and its number of vertices is at most n + m.
  • •
    Applications include collision detection, configuration space obstacles in motion planning, and fast combination of convex hulls.

Prerequisites

  • →Convexity and convex polygons — Understanding why the edge-merge algorithm works and why Minkowski sums of convex sets remain convex.
  • →Cross product and orientation in 2D — Angle comparison and inside-tests rely on cross product signs for robustness.
  • →Monotone chain convex hull — For general point sets you must convexify first before summing hulls.
  • →Point-in-convex polygon (binary search) — Collision detection reduces to checking whether the origin is inside the Minkowski sum.
  • →Floating-point stability and epsilons — Geometric predicates (collinearity, angle ordering) must tolerate numerical error.

Detailed Explanation

Tap terms for definitions

01Overview

The Minkowski sum is a way to combine two geometric sets by adding every point in one set to every point in the other. If you picture a shape A and a shape B on the plane, their Minkowski sum A ⊕ B is the set of all points a + b where a is from A and b is from B. While that sounds like a huge operation, there is a powerful simplification when both shapes are convex polygons: you can compute the result in linear time O(n + m), where n and m are the numbers of vertices in each polygon. The trick is to view each polygon as a loop of edge vectors (differences of consecutive vertices). When you sum polygons, their edge directions merge just like merging two sorted lists. This gives a simple, elegant algorithm based on geometry rather than brute force.

This concept has immediate applications in computational geometry and robotics. In collision detection, you can test if two convex shapes intersect by checking if the origin lies inside A ⊕ (−B). In robot motion planning, A ⊕ (−B) represents the “configuration space obstacle” for a robot B trying to navigate around A, turning collision checking into a single point-in-polygon query. In algorithms that deal with combining or translating shapes, Minkowski sums offer a reliable and efficient toolkit.

02Intuition & Analogies

Think of two stamps made of rubber: one shaped like A, one like B. Now, imagine sliding stamp B over every point of A and marking all the locations B’s reference point reaches. The cloud of ink marks you get is exactly the Minkowski sum A ⊕ B. If B is a disk, this looks like ‘inflating’ A by the disk’s radius, because the disk explores all directions uniformly around each point of A.

For convex polygons, picture walking around each polygon’s boundary in counterclockwise order, step by step. Each step is an edge vector with a certain direction (angle) and length. If you walk around A and B simultaneously, always taking the next step that turns the least in angle, your combined path traces the boundary of A ⊕ B. This is the same idea as merging two sorted lists: the edges are ‘sorted’ by their direction angle. Whenever both edges have the same angle, you take both at once, which just adds their lengths in that direction.

Collision intuition: placing shape B on top of A and asking, “Do they overlap?” is equivalent to fixing A in place and sliding the point (the origin) around A ⊕ (−B). If the origin can land inside this sum, B can be positioned to overlap A. This is why origin-inclusion decides collision. Finally, the idea that supports add—maximum projection of A ⊕ B in any direction equals the sum of maximal projections of A and B—explains both why the boundary is built by merging by angle and why convexity is preserved by Minkowski addition.

03Formal Definition

For subsets A, B of \(\), the Minkowski sum is defined as \(A B = \{\, a + b a A,\ b B \/\}\). If A and B are convex, then A ⊕ B is also convex. The support function of a set S in direction \(u \) is \((u) = \{ x, u : x S\}\). For Minkowski sums, support functions add: \((u) = (u) + (u)\). This identity characterizes the boundary’s normal directions and implies that the outer normal directions of A ⊕ B are the union (with multiplicities) of the normals of A and B. In the plane (), when A and B are convex polygons represented by their vertices in counterclockwise order, the boundary of A ⊕ B can be obtained by summing their edge vectors while scanning in increasing polar angle. If A has edges \(_0, , e^\) and B has edges \(_0, , e^\), all oriented counterclockwise, then the multiset of edges of A ⊕ B equals the angle-wise merge of \(\{_i\}\) and \(\{_j\}\), where equal angles are added component-wise. The number of vertices of A ⊕ B is at most n + m, with equality when no consecutive merged edges are collinear after addition.

04When to Use

Use the Minkowski sum when you need to combine shapes by translation in all possible ways. Typical scenarios:

  • Convex collision detection: A and B intersect iff (\mathbf{0} \in A \oplus (-B)). This converts a shape–shape test into a point-in-convex-polygon test, which can be done in O(log n) after O(n) preprocessing.
  • Robot motion planning and configuration space: For a robot B moving among obstacles A, inflating (dilating) each obstacle by −B gives A ⊕ (−B), so testing robot placements reduces to checking if the robot’s reference point is inside any inflated obstacle.
  • Combining convex hulls: For finite point sets P and Q, (\operatorname{conv}(P + Q) = \operatorname{conv}(P) \oplus \operatorname{conv}(Q)). If you only care about the convex hull of all pairwise sums, compute two convex hulls and then a linear-time Minkowski sum.
  • Offset operations: Approximating A ⊕ D_r, where D_r is a disk of radius r, produces an r-offset (dilation) of A. Replacing the disk by a k-gon approximates smooth offsets efficiently.
  • Support-mapping based algorithms: The additive property of support functions underlies algorithms like GJK/EPA; while they don’t explicitly build A ⊕ (−B), the theory is the same.

⚠️Common Mistakes

  • Not normalizing polygon order: The linear algorithm assumes both polygons are counterclockwise and start at the lexicographically smallest (lowest y, then lowest x) vertex. If you skip this, you may produce self-intersections or duplicate wrap-around edges.
  • Mishandling collinear edges: When consecutive edges have the same direction angle, you must merge them (add vectors) instead of emitting two separate steps. Forgetting this inflates vertex counts and creates redundant collinear vertices.
  • Floating-point robustness: Using strict angle comparisons (via atan2) or equality checks leads to instability. Prefer sign of cross products to compare angles, use an epsilon, and avoid computing angles at all when possible.
  • Forgetting to reorient −B: If B is CCW, the negated polygon −B will be clockwise; you must reverse its vertex order to recover CCW before summing.
  • Point-in-convex misclassification: A naive winding test can be O(n) and sensitive to collinearity. For repeated queries, use an O(log n) binary-search-based point-in-convex routine, and treat boundary points carefully with an epsilon.
  • Assuming results are simple even for non-convex inputs: The O(n + m) edge-merge algorithm requires convex inputs. For non-convex polygons, the Minkowski sum boundary can self-intersect and is more complex; first convexify with a hull if your application allows.

Key Formulas

Minkowski Sum Definition

Explanation: The Minkowski sum contains all vector sums of points from A and B. It combines shapes by translation in every possible way.

Support Function Additivity

Explanation: The farthest extent of A ⊕ B in direction u equals the sum of farthest extents of A and B. This underlies the angle-merge algorithm and explains convexity preservation.

Convex Hull of Pairwise Sums

Explanation: To get the convex hull of all pairwise sums of points from P and Q, you can first take convex hulls and then compute their Minkowski sum. This reduces complexity from quadratic to near-linear after hulls.

Time Complexity for Convex Polygons

Explanation: When inputs are convex polygons with n and m vertices in CCW order, the edge-merge algorithm traverses each list once. Thus the total running time is linear in the input sizes.

Orientation via Cross Product

Explanation: The sign of the 2D cross product indicates if c is to the left of ab (>0), on it (=0), or to the right (<0). This operation is used to compare edge angles robustly.

Collision Detection Equivalence

Explanation: Two sets intersect if and only if the origin lies in the Minkowski sum of A and the negation of B. This converts shape–shape collision into point-in-set testing.

Pairwise Sums Baseline

Explanation: Brute-force pairwise sums of two n-point sets take on the order of operations. Minkowski-sum-on-hulls avoids this quadratic blowup.

Polygon Area (Shoelace)

Explanation: The signed area helps detect CCW vs CW orientation (sign). We use it to normalize polygon orientation before merging edges.

Complexity Analysis

For convex polygons with n and m vertices, the standard Minkowski sum algorithm runs in O(n + m) time and O(n + m) space. The key is to preprocess each polygon by rotating it so that it starts from its lexicographically smallest vertex and ensuring counterclockwise order (O(n) time each). Then, build two lists of edge vectors and merge them by increasing polar angle. During merging, each edge is consumed at most once, so the main loop performs at most n + m increments, each with O(1) work using cross products for angle comparison. When two edge directions are equal (cross product is zero and dot product positive), we add both edges in a single step, preserving linear complexity. The space complexity is O(n + m) to store the input and output polygons and their edge lists. Additional working storage includes a small constant number of iterators and accumulators. If you perform a collinearity cleanup pass on the result (to remove redundant consecutive vertices), that pass is also linear in the output size. For collision detection via A ⊕ (−B), building the sum is O(n + m), while a point-in-convex-polygon test can be O(log (n + m)) per query after O(n + m) preprocessing, or O(n + m) if done naively. For general point sets P and Q, computing convex hulls first costs O( log + log ), after which the Minkowski sum is still O( + ), where h denotes hull size. In contrast, directly enumerating all pairwise sums of two k-point sets takes O() time and space, which is prohibitive. The convexity-based approach avoids this quadratic blowup whenever you only need the convex hull of the sum.

Code Examples

Minkowski sum of two convex polygons in O(n + m) by merging edge angles
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Pt {
5    long double x, y;
6    Pt() : x(0), y(0) {}
7    Pt(long double _x, long double _y) : x(_x), y(_y) {}
8    Pt operator+(const Pt& o) const { return Pt(x + o.x, y + o.y); }
9    Pt operator-(const Pt& o) const { return Pt(x - o.x, y - o.y); }
10    Pt operator*(long double k) const { return Pt(x * k, y * k); }
11    bool operator==(const Pt& o) const {
12        const long double EPS = 1e-12L;
13        return fabsl(x - o.x) <= EPS && fabsl(y - o.y) <= EPS;
14    }
15};
16
17static inline long double cross(const Pt& a, const Pt& b) { return a.x * b.y - a.y * b.x; }
18static inline long double dot(const Pt& a, const Pt& b) { return a.x * b.x + a.y * b.y; }
19
20long double polygon_area2(const vector<Pt>& P) {
21    long double s = 0; int n = (int)P.size();
22    for (int i = 0; i < n; ++i) {
23        int j = (i + 1) % n; s += cross(P[i], P[j]);
24    }
25    return s; // this is 2 * signed area
26}
27
28void ensure_ccw(vector<Pt>& P) {
29    if (P.size() <= 1) return;
30    if (polygon_area2(P) < 0) reverse(P.begin(), P.end());
31}
32
33int lexicographically_smallest_idx(const vector<Pt>& P) {
34    int n = (int)P.size(); int idx = 0;
35    for (int i = 1; i < n; ++i) {
36        if (P[i].y < P[idx].y || (P[i].y == P[idx].y && P[i].x < P[idx].x)) idx = i;
37    }
38    return idx;
39}
40
41void rotate_to_min_lex(vector<Pt>& P) {
42    if (P.empty()) return; int k = lexicographically_smallest_idx(P);
43    rotate(P.begin(), P.begin() + k, P.end());
44}
45
46// Remove consecutive collinear points and duplicate wrap-around
47vector<Pt> simplify_collinear(const vector<Pt>& P) {
48    int n = (int)P.size(); if (n <= 2) return P;
49    vector<Pt> Q;
50    for (int i = 0; i < n; ++i) {
51        Pt a = P[(i - 1 + n) % n];
52        Pt b = P[i];
53        Pt c = P[(i + 1) % n];
54        long double cr = cross(b - a, c - b);
55        if (fabsl(cr) > 1e-12L) Q.push_back(b); // keep non-collinear
56        else {
57            // If b is collinear, keep only if it's the only point between a and c (we can drop b)
58            // For convex polygons, dropping b is safe.
59        }
60    }
61    // Remove duplicate last==first if introduced
62    if (!Q.empty() && Q.front() == Q.back()) Q.pop_back();
63    return Q;
64}
65
66vector<Pt> edge_vectors(const vector<Pt>& P) {
67    int n = (int)P.size(); vector<Pt> E; E.reserve(n);
68    for (int i = 0; i < n; ++i) {
69        E.push_back(P[(i + 1) % n] - P[i]);
70    }
71    return E;
72}
73
74// Compare edge directions by polar angle without using atan2: return true if angle(a) <= angle(b)
75bool angle_leq(const Pt& a, const Pt& b) {
76    auto half = [](const Pt& v){ return (v.y > 0) || (v.y == 0 && v.x >= 0); };
77    bool ha = half(a), hb = half(b);
78    if (ha != hb) return ha; // upper half first
79    long double cr = cross(a, b);
80    if (fabsl(cr) > 1e-18L) return cr >= 0; // a is before b if it is counterclockwise to b
81    // same angle: tie by length (doesn't matter for ordering)
82    return dot(a, a) <= dot(b, b);
83}
84
85vector<Pt> minkowski_sum_convex(vector<Pt> A, vector<Pt> B) {
86    // Precondition: A, B are convex and CCW. We'll normalize.
87    ensure_ccw(A); ensure_ccw(B);
88    A = simplify_collinear(A); B = simplify_collinear(B);
89    rotate_to_min_lex(A); rotate_to_min_lex(B);
90
91    vector<Pt> EA = edge_vectors(A), EB = edge_vectors(B);
92    int n = (int)EA.size(), m = (int)EB.size();
93
94    vector<Pt> C; C.reserve(n + m + 5);
95    Pt cur = A[0] + B[0];
96    C.push_back(cur);
97    int i = 0, j = 0;
98    while (i < n || j < m) {
99        Pt ea = (i < n ? EA[i] : Pt(0,0));
100        Pt eb = (j < m ? EB[j] : Pt(0,0));
101        if (j == m || (i < n && angle_leq(ea, eb))) {
102            cur = cur + ea; ++i;
103        } else {
104            cur = cur + eb; ++j;
105        }
106        C.push_back(cur);
107    }
108
109    // Cleanup: remove collinear and possible duplicate last==first
110    C = simplify_collinear(C);
111    if (!C.empty() && C.front() == C.back()) C.pop_back();
112    return C;
113}
114
115int main() {
116    ios::sync_with_stdio(false);
117    cin.tie(nullptr);
118
119    // Example: rectangle A and diamond B
120    vector<Pt> A = { {0,0}, {3,0}, {3,1}, {0,1} }; // CCW rectangle
121    vector<Pt> B = { {0,1}, {1,0}, {0,-1}, {-1,0} }; // CCW diamond (rhombus)
122
123    vector<Pt> C = minkowski_sum_convex(A, B);
124
125    cout << fixed << setprecision(6);
126    cout << "A ⊕ B has " << C.size() << " vertices:\n";
127    for (auto &p : C) cout << p.x << " " << p.y << "\n";
128
129    return 0;
130}
131

This program implements the O(n + m) Minkowski sum for convex polygons by merging edge vectors in increasing polar angle. It normalizes polygons to CCW order, rotates them to start from the lexicographically smallest vertex, builds edge vectors, and merges them without using atan2 (using cross products instead). Consecutive collinear points are removed at the end to keep the polygon minimal.

Time: O(n + m)Space: O(n + m)
Convex collision detection via origin-inclusion of A ⊕ (−B)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Pt { long double x, y; };
5static inline Pt operator+(const Pt&a,const Pt&b){return {a.x+b.x,a.y+b.y};}
6static inline Pt operator-(const Pt&a,const Pt&b){return {a.x-b.x,a.y-b.y};}
7static inline bool eq(long double a,long double b){return fabsl(a-b)<=1e-12L;}
8static inline long double cross(const Pt&a,const Pt&b){return a.x*b.y-a.y*b.x;}
9static inline long double cross(const Pt&a,const Pt&b,const Pt&c){return cross(b-a,c-a);} // (b-a)x(c-a)
10
11long double area2(const vector<Pt>& P){ long double s=0; for(size_t i=0;i<P.size();++i){auto&u=P[i];auto&v=P[(i+1)%P.size()]; s+=cross(u,v);} return s; }
12void ensure_ccw(vector<Pt>& P){ if(P.size()>=3 && area2(P)<0) reverse(P.begin(),P.end()); }
13int lexmin(const vector<Pt>& P){ int k=0; for(int i=1;i<(int)P.size();++i){ if(P[i].y<P[k].y || (eq(P[i].y,P[k].y)&&P[i].x<P[k].x)) k=i; } return k; }
14void rotate_min(vector<Pt>& P){ if(P.empty()) return; rotate(P.begin(),P.begin()+lexmin(P),P.end()); }
15
16vector<Pt> simplify(const vector<Pt>& P){ int n=P.size(); if(n<=2) return P; vector<Pt> Q; Q.reserve(n);
17 for(int i=0;i<n;++i){ Pt a=P[(i-1+n)%n], b=P[i], c=P[(i+1)%n]; long double cr=cross(a,b,c); if(fabsl(cr)>1e-12L) Q.push_back(b); }
18 if(!Q.empty() && eq(Q.front().x,Q.back().x) && eq(Q.front().y,Q.back().y)) Q.pop_back(); return Q; }
19
20vector<Pt> edges(const vector<Pt>& P){ int n=P.size(); vector<Pt> E(n); for(int i=0;i<n;++i) E[i]=P[(i+1)%n]-P[i]; return E; }
21bool half(const Pt&v){ return (v.y>0) || (eq(v.y,0)&&v.x>=0); }
22bool angle_leq(const Pt&a,const Pt&b){ bool ha=half(a), hb=half(b); if(ha!=hb) return ha; long double cr=cross(a,b); if(fabsl(cr)>1e-18L) return cr>=0; return (a.x*a.x+a.y*a.y) <= (b.x*b.x+b.y*b.y); }
23
24vector<Pt> minkowski_sum_convex(vector<Pt> A, vector<Pt> B){ ensure_ccw(A); ensure_ccw(B); A=simplify(A); B=simplify(B); rotate_min(A); rotate_min(B);
25 auto EA=edges(A), EB=edges(B); int n=EA.size(), m=EB.size();
26 vector<Pt> C; C.reserve(n+m+5); Pt cur=A[0]+B[0]; C.push_back(cur); int i=0,j=0;
27 while(i<n||j<m){ Pt ea=(i<n?EA[i]:Pt{0,0}), eb=(j<m?EB[j]:Pt{0,0}); if(j==m || (i<n && angle_leq(ea,eb))){ cur=cur+ea; ++i; } else { cur=cur+eb; ++j; } C.push_back(cur); }
28 C=simplify(C); if(!C.empty() && eq(C.front().x,C.back().x) && eq(C.front().y,C.back().y)) C.pop_back(); return C; }
29
30vector<Pt> negate_polygon_ccw(vector<Pt> P){ for(auto &p:P){ p.x=-p.x; p.y=-p.y; } // Negation flips orientation; restore CCW
31 if(P.size()>=3 && area2(P)>0) reverse(P.begin(),P.end()); // area2>0 means already CCW for original; after negation it's CW
32 ensure_ccw(P); return P; }
33
34// Point-in-convex: returns 1 inside, 0 on boundary, -1 outside. P must be CCW and strictly convex (collinear simplified).
35int point_in_convex(const vector<Pt>& P, Pt q){
36    int n=P.size(); if(n==0) return -1; if(n==1){ if(eq(P[0].x,q.x)&&eq(P[0].y,q.y)) return 0; return -1; }
37    if(n==2){ long double cr=fabsl(cross(P[0],P[1],q)); if(cr>1e-12L) return -1; // not on line
38        // Check projection on segment
39        long double dx1=q.x-P[0].x, dy1=q.y-P[0].y; long double dx2=P[1].x-P[0].x, dy2=P[1].y-P[0].y;
40        long double t=(dx1*dx2+dy1*dy2)/(dx2*dx2+dy2*dy2);
41        return (t>=-1e-12L && t<=1+1e-12L) ? 0 : -1; }
42    // q must be between rays P0->P1 and P0->P{n-1}
43    if (cross(P[0], P[1], q) < -1e-12L) return -1;
44    if (cross(P[0], P[n-1], q) > 1e-12L) return -1;
45    // Binary search sector
46    int l=1, r=n-1; while(r-l>1){ int mid=(l+r)/2; if(cross(P[0], P[mid], q) >= 0) l=mid; else r=mid; }
47    long double s = cross(P[l], P[(l+1)%n], q);
48    if (fabsl(s) <= 1e-12L) return 0; // on boundary of triangle
49    return (s > 0 ? 1 : -1);
50}
51
52int main(){
53    ios::sync_with_stdio(false); cin.tie(nullptr);
54
55    // Define two convex polygons A and B
56    vector<Pt> A = { {0,0}, {4,0}, {4,2}, {0,2} }; // rectangle
57    vector<Pt> B = { {1,1}, {2,0}, {1,-1}, {0,0} }; // rhombus translated to avoid symmetry
58
59    // Build C = A ⊕ (−B)
60    vector<Pt> negB = negate_polygon_ccw(B);
61    vector<Pt> C = minkowski_sum_convex(A, negB);
62
63    // Test if origin lies inside C
64    int rel = point_in_convex(C, {0,0});
65    cout << (rel>=0 ? "Collision (origin in A ⊕ (−B))\n" : "No collision\n");
66
67    // For visibility, print result polygon
68    cout << fixed << setprecision(6);
69    cout << "|C| = " << C.size() << "\n";
70    for(auto&p:C) cout<<p.x<<" "<<p.y<<"\n";
71}
72

This program detects whether two convex polygons intersect by computing C = A ⊕ (−B) and checking if the origin is inside C. It includes a robust point-in-convex test using a binary search on a fan from the first vertex, handling boundary cases. The −B polygon is negated and reoriented to CCW before summing.

Time: O(n + m) to build the sum, O(log(n + m)) for the point-in-convex testSpace: O(n + m)
Convex hull of pairwise sums via conv(P) ⊕ conv(Q)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Pt{
5    long double x,y; };
6static inline Pt operator+(const Pt&a,const Pt&b){return {a.x+b.x,a.y+b.y};}
7static inline Pt operator-(const Pt&a,const Pt&b){return {a.x-b.x,a.y-b.y};}
8static inline bool eq(long double a,long double b){return fabsl(a-b)<=1e-12L;}
9static inline long double cross(const Pt&a,const Pt&b){return a.x*b.y-a.y*b.x;}
10static inline long double cross(const Pt&a,const Pt&b,const Pt&c){return cross(b-a,c-a);} // (b-a)x(c-a)
11
12// Monotone chain convex hull (keeps no collinear interior points)
13vector<Pt> convex_hull(vector<Pt> P){
14    sort(P.begin(),P.end(),[](const Pt&a,const Pt&b){return a.x<b.x || (eq(a.x,b.x)&&a.y<b.y);} );
15    P.erase(unique(P.begin(),P.end(),[](const Pt&a,const Pt&b){return eq(a.x,b.x)&&eq(a.y,b.y);} ),P.end());
16    int n=P.size(); if(n<=1) return P;
17    vector<Pt> L,U;
18    for(auto&p:P){ while(L.size()>=2 && cross(L[L.size()-2],L.back(),p) <= 1e-12L) L.pop_back(); L.push_back(p); }
19    for(int i=n-1;i>=0;--i){ auto p=P[i]; while(U.size()>=2 && cross(U[U.size()-2],U.back(),p) <= 1e-12L) U.pop_back(); U.push_back(p); }
20    L.pop_back(); U.pop_back();
21    L.insert(L.end(), U.begin(), U.end());
22    return L; // CCW without collinear edges
23}
24
25int lexmin(const vector<Pt>& P){int k=0; for(int i=1;i<(int)P.size();++i){ if(P[i].y<P[k].y || (eq(P[i].y,P[k].y)&&P[i].x<P[k].x)) k=i; } return k; }
26void rotate_min(vector<Pt>& P){ if(P.empty())return; rotate(P.begin(),P.begin()+lexmin(P),P.end()); }
27vector<Pt> edges(const vector<Pt>& P){ int n=P.size(); vector<Pt> E(n); for(int i=0;i<n;++i) E[i]=P[(i+1)%n]-P[i]; return E; }
28bool half(const Pt&v){ return (v.y>0) || (eq(v.y,0)&&v.x>=0); }
29static inline long double crossv(const Pt&a,const Pt&b){return a.x*b.y-a.y*b.x;}
30bool angle_leq(const Pt&a,const Pt&b){ bool ha=half(a), hb=half(b); if(ha!=hb) return ha; long double cr=crossv(a,b); if(fabsl(cr)>1e-18L) return cr>=0; return (a.x*a.x+a.y*a.y) <= (b.x*b.x+b.y*b.y); }
31
32vector<Pt> simplify(const vector<Pt>& P){ int n=P.size(); if(n<=2) return P; vector<Pt> Q; Q.reserve(n);
33 for(int i=0;i<n;++i){ Pt a=P[(i-1+n)%n], b=P[i], c=P[(i+1)%n]; long double cr=cross(a,b,c); if(fabsl(cr)>1e-12L) Q.push_back(b); }
34 if(!Q.empty() && eq(Q.front().x,Q.back().x) && eq(Q.front().y,Q.back().y)) Q.pop_back(); return Q; }
35
36vector<Pt> minkowski_sum_convex(vector<Pt> A, vector<Pt> B){ rotate_min(A); rotate_min(B); auto EA=edges(A), EB=edges(B); int n=EA.size(), m=EB.size(); vector<Pt> C; C.reserve(n+m+5); Pt cur=A[0]+B[0]; C.push_back(cur); int i=0,j=0; while(i<n||j<m){ Pt ea=(i<n?EA[i]:Pt{0,0}), eb=(j<m?EB[j]:Pt{0,0}); if(j==m || (i<n && angle_leq(ea,eb))){ cur=cur+ea; ++i; } else { cur=cur+eb; ++j; } C.push_back(cur);} return simplify(C); }
37
38int main(){
39    ios::sync_with_stdio(false); cin.tie(nullptr);
40
41    // Input two point clouds, build hulls, then compute hull of pairwise sums
42    int n=6, m=5; // example sizes
43    vector<Pt> P = {{0,0},{2,0},{1,1},{2,2},{0,2},{1,3}};
44    vector<Pt> Q = {{-1,0},{0,1},{1,0},{0,-1},{2,1}};
45
46    auto HP = convex_hull(P); // CCW hull of P
47    auto HQ = convex_hull(Q); // CCW hull of Q
48
49    auto S = minkowski_sum_convex(HP, HQ);
50
51    cout << fixed << setprecision(6);
52    cout << "|conv(P)| = " << HP.size() << ", |conv(Q)| = " << HQ.size() << "\n";
53    cout << "|conv(P)+conv(Q)| = " << S.size() << "\n";
54    for(auto &p:S) cout << p.x << " " << p.y << "\n";
55}
56

This program computes the convex hull of two point sets using the monotone chain algorithm and then computes their Minkowski sum in linear time. By the identity conv(P + Q) = conv(P) ⊕ conv(Q), the result is the convex hull of all pairwise sums without enumerating O(nm) pairs.

Time: O(n log n + m log m) for hulls and O(h_P + h_Q) for the Minkowski sumSpace: O(n + m)