1. Formal Invariant — Monotone Chain Stack Convexity & Antipodal Pairs
Invariant 1: Andrew's Monotone Chain Stack Property
After sorting distinct points $P_0 < P_1 < \dots < P_{N-1}$ lexicographically by $(x, y)$, both the Lower Hull and Upper Hull stacks satisfy the strict CCW invariant on every consecutive triple $(H_{k-2}, H_{k-1}, H_k)$:
$$\text{cross}(H_{k-2},\; H_{k-1},\; P_i) > 0$$
Whenever $\text{cross}(H_{k-2}, H_{k-1}, P_i) \le 0$ (a right turn or collinear point), $H_{k-1}$ lies inside or on the boundary of $\triangle H_{k-2} H_0 P_i$ and is permanently popped from the hull stack.
Invariant 2: Rotating Calipers Area Monotonicity
On a convex hull $H_0, \dots, H_{M-1}$ in CCW order, for a directed base edge $\vec{e}_i = H_{i+1} - H_i$, the triangle area $\text{cross}(H_i, H_{i+1}, H_j)$ is unimodal as $j$ advances around the hull, allowing the antipodal pointer $j$ to advance monotonically in $O(M)$ total steps.
Trace 2D cross-product orientation tests cross(O, A, B) = (Ax-Ox)(By-Oy) - (Ay-Oy)(Bx-Ox) to prune clockwise interior vertices and detect sweep-line segment intersections.
Invariant & State
2. Andrew's Monotone Chain & Rotating Calipers Pipeline
& Deduplicate O(N log N)"] SortLex --> Lower["Sweep Left-to-Right:
Pop while cross <= 0
(Builds Lower Hull)"] SortLex --> Upper["Sweep Right-to-Left:
Pop while cross <= 0
(Builds Upper Hull)"] Lower --> Concat["Concatenate Lower + Upper
Into CCW Convex Hull (Size H)"] Upper --> Concat Concat --> Calipers["Rotating Calipers Two-Pointer:
Advance j while cross(e_i, H_{j+1}-H_j) > 0
O(H) Diameter"]
3. Why Andrew's Monotone Chain Beats Graham Scan in Practice
- Faster Sorting Key: Comparing two integers
a.x < b.x || (a.x == b.x && a.y < b.y)takes 1–2 CPU cycles and branches predictably, whereas Graham Scan's polar comparator requires a 64-bit cross product + distance tie-breaker on everystd::sortcomparison ($O(N \log N)$ multiplications). - Clean Collinear Handling: In Graham Scan, collinear points along the final closing ray back to the pivot require reversing the suffix of the sorted array if you want all boundary points. In Andrew's Monotone Chain, simply changing
< 0vs<= 0in thewhileloop toggles between keeping or discarding collinear boundary vertices!
4. Hardware & Cache Reality
Amortized $O(N)$ Stack Scans & SIMD Sorting
After the initial $O(N \log N)$ sort, the lower and upper hull construction loops stream sequentially through pts[0..N-1] and push/pop at the tail of a single contiguous std::vector<Point>. Each point is pushed twice and popped at most twice ($\le 4N$ stack ops total), executing in sub-millisecond L1 cache time.
5. Complexity Matrix
| Algorithm | Time Complexity | Space Complexity | Best Suited When |
|---|---|---|---|
| Andrew's Monotone Chain | O(N log N) | O(N) | General 2D Convex Hull ($O(N)$ if pre-sorted by $x$) |
| Graham Scan | O(N log N) | O(N) | Radially sorted point sets |
| Jarvis March (Gift Wrapping) | O(N * H) | O(H) | Output-sensitive when hull size $H \ll \log N$ |
| Chan's Algorithm | O(N log H) | O(N) | Optimal output-sensitive 2D/3D Convex Hull |
| Rotating Calipers (Diameter / Width) | O(H) after hull | O(1) | Farthest pair of points, minimum bounding box |
6. Production-Grade C++20 Implementation (Monotone Chain + Rotating Calipers Diameter)
#include <vector>
#include <cstdint>
#include <algorithm>
struct Pt {
int64_t x = 0, y = 0;
bool operator<(const Pt& o) const { return x != o.x ? x < o.x : y < o.y; }
bool operator==(const Pt& o) const { return x == o.x && y == o.y; }
Pt operator-(const Pt& o) const { return {x - o.x, y - o.y}; }
};
inline int64_t cross(const Pt& a, const Pt& b, const Pt& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline int64_t dist_sq(const Pt& a, const Pt& b) {
int64_t dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
// Returns strictly convex hull in CCW order (no 3 collinear points)
std::vector<Pt> monotone_chain_hull(std::vector<Pt> pts) {
std::sort(pts.begin(), pts.end());
pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
const int n = static_cast<int>(pts.size());
if (n <= 1) return pts;
std::vector<Pt> hull;
hull.reserve(2 * n);
// Lower hull
for (int i = 0; i < n; ++i) {
while (hull.size() >= 2 &&
cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
hull.pop_back();
}
hull.push_back(pts[i]);
}
// Upper hull
const std::size_t lower_sz = hull.size();
for (int i = n - 2; i >= 0; --i) {
while (hull.size() > lower_sz &&
cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
hull.pop_back();
}
hull.push_back(pts[i]);
}
hull.pop_back(); // Last point duplicates pts[0]
return hull;
}
// Rotating Calipers: Returns maximum squared Euclidean distance (Diameter^2) in O(H)
int64_t rotating_calipers_diameter_sq(const std::vector<Pt>& hull) {
const int h = static_cast<int>(hull.size());
if (h <= 1) return 0;
if (h == 2) return dist_sq(hull[0], hull[1]);
int64_t max_d2 = 0;
int j = 1;
for (int i = 0; i < h; ++i) {
int ni = (i + 1) % h;
// Advance antipodal vertex j while triangle area increases
while (cross(hull[i], hull[ni], hull[(j + 1) % h]) >
cross(hull[i], hull[ni], hull[j])) {
j = (j + 1) % h;
}
max_d2 = std::max({max_d2, dist_sq(hull[i], hull[j]), dist_sq(hull[ni], hull[j])});
}
return max_d2;
}Production Pitfall — Advancing Rotating Calipers by Euclidean Distance Instead of Cross-Product Area
When implementing Rotating Calipers for the farthest pair of points, a classic mistake is advancing pointer j while dist_sq(hull[i], hull[j+1]) > dist_sq(hull[i], hull[j]). Squared distance from a single vertex hull[i] is NOT necessarily unimodal around an arbitrary convex polygon, and two-pointer advancing on dist_sq fails on elongated polygons! Always advance j by comparing perpendicular height (triangle area) cross(hull[i], hull[i+1], hull[j]) against the base edge $\overline{H_i H_{i+1}}$, which is strictly unimodal on any convex hull.