AntInLoop

Rotating Calipers (Diameter of a Convex Polygon)

Rotating Calipers sweeps antipodal pairs around a convex polygon in linear O(n) time to find the farthest pair of points (diameter), polygon width, and minimum-area enclosing rectangle.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Rotating Calipers (Diameter of a Convex Polygon)

Rotating Calipers is the geometric equivalent of Two Pointers around a convex polygon! Imagine placing two parallel lines touching opposite sides of a convex hull and rotating them $360^\circ$. Because the farthest vertex j from edge (i, i + 1) moves monotonically around the hull as i advances, all antipodal pairs are visited in $O(n)$ time—finding the diameter (farthest pair of points) of $n$ 2D points in $O(n \log n)$ total time!

At a Glance

| Property | Value |

| :--- | :---: |

| Hull Construction | $O(n \log n)$ via Convex Hull |

| Calipers Sweep | $O(n)$ (pointer j wraps at most once) |

| Best Used When | Farthest pair of points, polygon width, minimum bounding rectangle |

---

Practice Problems

Hard

1. Farthest Pair of Points in 2D (Squared Diameter)

Given $n$ 2D points, find the maximum squared Euclidean distance between any two points in $O(n \log n)$ time.

Approach: Compute the CCW Convex Hull h (size m). For each edge h[i] -> h[(i + 1) % m], advance j while the triangle area abs(cross(h[i], h[ni], h[nj])) increases, updating best = max(best, distSq(h[i], h[j]), distSq(h[ni], h[j])). Time: $O(n \log n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

struct Pt {
    long long x, y;
    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; }
};

long long cross(const Pt& O, const Pt& A, const Pt& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
long long distSq(const Pt& a, const Pt& b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

long long maxDistSq(std::vector<Pt> pts) {
    std::sort(pts.begin(), pts.end());
    pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
    int n = static_cast<int>(pts.size());
    if (n <= 1) return 0;
    if (n == 2) return distSq(pts[0], pts[1]);

    std::vector<Pt> h;
    for (const auto& p : pts) {
        while (h.size() >= 2 && cross(h[h.size() - 2], h.back(), p) <= 0) h.pop_back();
        h.push_back(p);
    }
    size_t low = h.size();
    for (int i = n - 2; i >= 0; --i) {
        while (h.size() > low && cross(h[h.size() - 2], h.back(), pts[i]) <= 0) h.pop_back();
        h.push_back(pts[i]);
    }
    h.pop_back();

    int m = static_cast<int>(h.size());
    long long best = 0;
    for (int i = 0, j = 1; i < m; ++i) {
        int ni = (i + 1) % m;
        while (std::abs(cross(h[i], h[ni], h[(j + 1) % m])) > std::abs(cross(h[i], h[ni], h[j]))) {
            j = (j + 1) % m;
        }
        best = std::max({best, distSq(h[i], h[j]), distSq(h[ni], h[j])});
    }
    return best;
}

int main() {
    std::cout << maxDistSq({{0, 0}, {3, 0}, {3, 4}, {0, 4}, {1, 2}}) << "\n"; // 3^2 + 4^2 = 25
    return 0;
}

</details>

---

Related Algorithms