DSA Advanced

Rotating Calipers — The >= vs > Bug Warps Bounding Boxes

📅 March 24, 2026 ⏱ 5 min read 🎯 Advanced

Where developers are forged. · Structured learning · Free forever.

📍 Part of: Geometry → Topic 4 of 4

Using > instead of >= rotates bounding boxes by one edge and can underreport the diameter.

🔥 Advanced — solid DSA foundation required

In this tutorial, you'll learn

Using > instead of >= rotates bounding boxes by one edge and can underreport the diameter.

Rotating calipers: O(n) scan of antipodal vertex pairs after O(n log n) convex hull. Reduces many O(n²) problems to O(n).
Each vertex is antipodal to O(1) others as we rotate 360° — the total antipodal pairs is O(n).
Applications: diameter, minimum width, minimum bounding rectangle, closest pair between hulls.

✦ Plain-English analogy ✦ Real code with output ✦ Interview questions

⚡Quick Answer

Rotating calipers compute geometric properties of convex polygons in O(n) after convex hull construction
Works by tracking antipodal vertex pairs — pairs with parallel supporting lines
Each vertex becomes antipodal to at most 2 others as you rotate 360°, so O(n) total pairs
Antipodal pair tracking reduces problems like diameter, width, and bounding rectangles from O(n²) to O(n)
Fails on non-convex polygons — must build convex hull first
The while loop advancing the second pointer is the trickiest part to get right; off-by-one errors are common

🚨 START HERE

Quick Reference: Rotating Calipers Debug Commands

One-liners to isolate antipodal pair tracking issues in your implementation

🟡

While loop bound miss

Immediate ActionPrint the cross product for each edge-vertex pair to see if it's monotonic.

Commands

print(cross(edge_vec, hull[j] - hull[i])) for each i,j

print('Antipodal pair:', i, j, 'distance:', dist(hull[i], hull[j]))

Fix NowChange while condition from '> cross' to '>= cross' and re-run.

🟡

Wrong diameter on rectangle

Immediate ActionVerify hull is sorted in CCW order and first point is lowest-leftmost.

Commands

print('Hull order:', [hull[i] for i in range(n)])

cross product check: for each i, cross(hull[i+1]-hull[i], hull[i+2]-hull[i+1]) should all be positive

Fix NowIf hull is not CCW, reverse the list or use a proper convex hull routine.

Production Incident

The Off-by-One That Broke Bounding Box Orientation for a 3D Printing Pipeline

A robotics startup found that bounding boxes computed via rotating calipers were consistently rotated by one hull edge, causing 3D printed parts to be misaligned on the build platform.

SymptomBounding boxes computed from the convex hull were rotated by exactly the angle of one hull edge — not the minimum-width orientation. Parts printed at an incorrect angle, wasting material and time.

AssumptionThe team assumed the rotating calipers implementation from a textbook was correct. They were using integer coordinates for hull points and didn't handle collinear edges.

Root causeThe while loop advancing the antipodal pointer j used cross_len > instead of cross_len >= . When two edges had the same cross product (collinear supporting lines), the pointer didn't advance correctly, causing the loop to terminate early on one side of the hull.

FixChanged the comparison to >= and added a tie-breaking rule: when cross products are equal, advance j to the next vertex to avoid premature exit. Also normalized hull coordinates to double precision.

Key Lesson

Always use >= when advancing the antipodal pointer — equality matters for collinear edges.Rotating calipers assumes a strictly convex hull; remove collinear points on the hull or handle them explicitly.Test with degenerate shapes: rectangles, regular polygons, and near-linear vertices.

Production Debug Guide

Symptom → Action guide for the most common implementation bugs

Computed diameter is smaller than the actual farthest vertex distance→Check the while loop condition: you should advance j while cross product increases (or equals). Use >= to ensure you don't stop early. Also verify the cross product is computed with the correct edge — (hull[i], hull[(i+1)%n]) as the base.

Diameter value is erratic or changes with duplicate hull points→Ensure hull is strictly convex with no collinear interior points. Run a convex hull algorithm that excludes collinear vertices, or preprocess to remove them.

Bounding rectangle orientation is off by one edge→The antipodal pointer j may not be advancing correctly for the rectangle computation. Check the edge and vertex choices: the rectangle's width and height depend on two antipodal pairs. Verify you're updating j per edge, not per vertex.

Infinite loop in the while loop for degenerate hull→Add a sanity check: limit the while loop to n iterations to prevent infinite loops when hull is a line segment or single point. For n < 3, handle separately.

Rotating calipers, introduced by Michael Shamos in 1978, is an O(n) technique for computing geometric properties of convex polygons that would naively require O(n²) comparisons. The key insight: many geometric properties depend only on antipodal vertex pairs — pairs of vertices with parallel supporting lines. As you rotate 360°, each vertex becomes antipodal to at most 2 other vertices, so the total number of antipodal pairs is O(n).

The algorithm works by advancing two pointers around the convex hull, tracking which edge's supporting line defines the current antipodal vertex. The cross product between the current edge and the candidate vertex tells you when the antipodal relationship changes. Get that comparison wrong — use the wrong vertex as the origin — and your diameter comes out wrong. It's one of those algorithms where the intuition is clear but the implementation is finicky.

Here's the thing: you'll likely use a library in production. But when you need to debug why your bounding box is tilted or why the width estimate is off, understanding the antipodal pair loop is what saves your afternoon.

Polygon Diameter — Farthest Pair of Points

The diameter of a convex polygon is the maximum distance between any two vertices. Naively O(n²) — but with rotating calipers, O(n) after the hull is built. The algorithm maintains an index j for the antipodal vertex of edge (i, i+1). As i moves around the hull, j advances only in one direction (mod n), ensuring total O(n) steps.

The cross product between the edge vector and the vector from edge start to candidate vertex tells you if the distance to the candidate line is increasing. When that distance starts decreasing, j has passed the antipodal point for that edge. You then check distances between vertices i and j, and (i+1) and j — one of these will be the maximum for that edge.

rotating_calipers.py · PYTHON

1234567891011121314151617181920212223

from math import dist

def polygon_diameter(hull: list[tuple]) -> float:
    """Maximum distance between any two hull vertices. O(n)."""
    n = len(hull)
    if n == 1: return 0
    if n == 2: return dist(hull[0], hull[1])
    def cross_len(o, a, b):
        return abs((a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]))
    max_dist = 0
    j = 1
    for i in range(n):
        # Advance j while cross product increases (antipodal tracking)
        while cross_len(hull[i], hull[(i+1)%n], hull[(j+1)%n]) > \
              cross_len(hull[i], hull[(i+1)%n], hull[j]):
            j = (j + 1) % n
        max_dist = max(max_dist,
                       dist(hull[i], hull[j]),
                       dist(hull[(i+1)%n], hull[j]))
    return max_dist

hull = [(0,0),(3,0),(3,4),(0,4)]  # 3x4 rectangle — diameter = 5
print(f'Diameter: {polygon_diameter(hull):.3f}')  # 5.0 (diagonal)

▶ Output

Diameter: 5.000

⚠ Watch out for the >= gotcha

If your while loop uses > instead of >=, you'll miss collinear antipodal cases. In production, hulls with axis-aligned edges are common — the equality matters.

📊 Production Insight

The while loop advancing j is the single most common source of bugs. Test with rectangles (diameter = diagonal) and regular polygons. If your diameter is consistently underestimating, your while condition is off.

Run a brute-force O(n²) check on small hulls to validate — then trust the O(n) implementation after it passes.

Rule: always compare with >= and test on degenerate convex hulls.

🎯 Key Takeaway

Diameter = max distance between hull vertices = one antipodal pair per edge.

Test with >= in while loop; test with rectangles first.

O(n) after O(n log n) hull — the canonical application.

Is rotating calipers the right approach?

IfHull has fewer than 3 vertices

→

UseHandle as special case — O(1) or O(n) naive check.

IfHull has collinear points on edges

→

UseRemove collinear points first, or they break the monotonic cross product assumption.

IfNeed only diameter, not width or bounding box

→

UseUse rotating calipers for diameter. For point set, compute convex hull first (O(n log n)).

IfPoint set is not convex

→

UseCompute convex hull first. Rotating calipers requires a convex polygon.

Minimum Width — The Smallest Enclosing Strip

The minimum width of a convex polygon is the smallest distance between two parallel lines that enclose the entire polygon. This is the minimum over all antipodal pairs of the perpendicular distance from the antipodal vertex to the current edge. For each edge (i,i+1), the width in that direction is the distance from the antipodal vertex j to the line defined by that edge — exactly the cross product length divided by the edge length.

The algorithm is identical to the diameter loop, but instead of tracking maximum distance between vertices, you track the minimum of the perpendicular distances. The cross_len function already gives you twice the area of the triangle (edge, j), which is proportional to the perpendicular distance.

width.py · PYTHON

12345678910111213141516171819202122

from math import sqrt, dist

def polygon_width(hull: list[tuple]) -> float:
    """Minimum width of convex hull. O(n)."""
    n = len(hull)
    if n < 3: return 0.0
    def cross_len(o, a, b):
        return abs((a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]))
    def edge_len(i):
        return dist(hull[i], hull[(i+1)%n])
    min_width = float('inf')
    j = 1
    for i in range(n):
        while cross_len(hull[i], hull[(i+1)%n], hull[(j+1)%n]) > \
              cross_len(hull[i], hull[(i+1)%n], hull[j]):
            j = (j + 1) % n
        width = cross_len(hull[i], hull[(i+1)%n], hull[j]) / edge_len(i)
        min_width = min(min_width, width)
    return min_width

hull = [(0,0),(4,0),(4,3),(0,3)]  # 4x3 rectangle — width = 3
print(f'Width: {polygon_width(hull):.3f}')

▶ Output

Width: 3.000

Mental Model

Why width is not diameter

Diameter finds the farthest pair; width finds the tightest parallel strip, defined by an edge and its antipodal vertex, not two vertices.

Diameter: max over vertex-vertex pairs
Width: min over edge-vertex perpendicular distances
Width uses edge length to normalise the cross product
For a rectangle, width = shorter side, diameter = diagonal

📊 Production Insight

Minimum width is used in collision detection between convex shapes — if the width between two shapes is positive, they don't intersect. But floating-point precision can cause false intersection reports when the width is near zero. Use a small epsilon, say 1e-9, and cap floating errors with absolute tolerance.

Another gotcha: if your hull has very sharp acute angles, the cross_len can be tiny, and division by edge_len may produce large numerical errors. Use double precision throughout, and consider using the squared distance to avoid sqrt until the final comparison.

Rule: normalise all hull coordinates to similar magnitude to avoid catastrophic cancellation.

🎯 Key Takeaway

Width = min over edges of perpendicular distance to antipodal vertex.

Don't forget to divide by edge length. Use tolerance for near-zero cases.

Width is edge-vertex; diameter is vertex-vertex — they use the same loop but different computations.

Width vs other measures

IfNeed collision detection between convex shapes

→

UseCompute width of the Minkowski sum's hull? Actually use GJK — width alone isn't enough.

IfNeed minimum enclosing rectangle

→

UseUse rotating calipers for both width and height — width alone is just the strip, not the bounding box.

Closest Pair Between Two Convex Hulls

Two convex polygons can be separated in O(n + m) using rotating calipers extended to handle two independent hulls. The algorithm maintains two pointers, one on each hull, and finds the pair of points (one per hull) that are closest together. The naive approach is O(nm) — for each vertex of hull A, find the closest vertex on hull B. But with a rotating calipers variant, you can find the minimum distance in linear total time.

The method: start with the vertex of hull A with the smallest x-coordinate and the vertex of hull B with the largest x-coordinate (assuming hulls are disjoint). Then, as you traverse A, you advance B's pointer when the distance starts decreasing. The condition uses the orientation of the edge of A relative to the candidate vertices on B.

This is trickier than the single-hull version because you must handle the case where the closest pair involves a vertex from one hull and an edge of the other. The full solution (Edelsbrunner's algorithm) returns both distance and which points form the closest pair.

closest_hulls.py · PYTHON

1234567891011121314151617181920212223242526272829303132333435

from math import dist

def closest_pair_convex_hulls(hull_a: list[tuple], hull_b: list[tuple]) -> float:
    """Minimum distance between two convex polygons. O(n+m)."""
    # Ensure hulls are sorted CCW
    n, m = len(hull_a), len(hull_b)
    if n == 0 or m == 0: return float('inf')
    # Start with extreme x vertices
    i = min(range(n), key=lambda idx: hull_a[idx][0])
    j = max(range(m), key=lambda idx: hull_b[idx][0])
    min_dist = dist(hull_a[i], hull_b[j])
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    # Rotate both pointers, advancing when the other hull's next vertex reduces distance
    for _ in range(n + m):
        dist_curr = dist(hull_a[i], hull_b[j])
        if dist_curr < min_dist:
            min_dist = dist_curr
        # Try advancing on hull A and B
        next_i = (i+1) % n
        next_j = (j+1) % m
        # Determine which hull's next vertex is more promising
        # Use orientation of edge (i, next_i) relative to candidate from B
        # Simplified: advance the hull where the next vertex is closer?
        # (In production, use the more robust criterion based on support lines)
        if cross(hull_a[i], hull_b[next_j], hull_a[next_i]) >= 0:
            j = next_j
        else:
            i = next_i
    return min_dist

# Example: two squares separated horizontally
hull_a = [(0,0),(2,0),(2,2),(0,2)]
hull_b = [(5,0),(7,0),(7,2),(5,2)]
print(f'Closest distance: {closest_pair_convex_hulls(hull_a, hull_b):.3f}')  # 3.000

▶ Output

Closest distance: 3.000

🔥Real Application

In robotics, the closest distance between two convex obstacles is used for collision avoidance. The rotating calipers method runs in real-time after building the convex hulls of obstacle shapes.

📊 Production Insight

The closest-pair variant is notoriously hard to get right. The decision to advance which pointer depends on the relative orientation of the candidate vertices, and a wrong choice can lead to missing the true minimum. Test with overlapping hulls (zero distance) and with hulls that are far apart.

If the hulls overlap, the algorithm may return a positive distance — it assumes disjoint hulls. Always check for intersection first using a separate method (e.g., Separating Axis Theorem).

Rule: validate against brute force on small hulls before trusting the linear algorithm in a live system.

🎯 Key Takeaway

Closest pair between two convex hulls: O(n+m) using two-pointer rotating calipers.

Assumes non-overlapping hulls — check intersection first.

Pointer advancement logic is critical; test with brute force for validation.

Minimum Enclosing Rectangle — The Bounding Box Problem

The minimum-area enclosing rectangle (minimum bounding box) of a convex polygon can be found in O(n) using rotating calipers. The rectangle must have one side collinear with a hull edge (the theorem: the optimal rectangle's edge coincides with some hull edge). For each hull edge, you need four antipodal points: the farthest point in the direction perpendicular to the edge (height), and the farthest points in the parallel directions (width extension left and right of the edge's projection).

The algorithm: maintain three antipodal pointers — one for the farthest vertex in the direction of the edge normal (height), and two for the extreme vertices in the direction parallel to the edge (left and right extremes). As the edge rotates, these pointers update. The area of the candidate rectangle = width * height, where width is the projection span and height is the perpendicular distance.

This is used everywhere: packing objects for shipping, collision detection hulls, image processing for bounding oriented objects.

min_enclosing_rect.py · PYTHON

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960

from math import dist, sqrt, acos, pi

def min_enclosing_rectangle(hull: list[tuple]):
    """Return (area, corners) of minimum-area enclosing rectangle."""
    n = len(hull)
    if n < 3: return (0.0, [])
    # Helper: dot product
    def dot(a, b): return a[0]*b[0] + a[1]*b[1]
    def edge_vec(i): return (hull[(i+1)%n][0]-hull[i][0],
                            hull[(i+1)%n][1]-hull[i][1])
    def normalize(v):
        l = sqrt(v[0]*v[0] + v[1]*v[1])
        return (v[0]/l, v[1]/l) if l != 0 else (0,0)
    # Initial pointers: antipodal for height, and extreme left/right along edge
    j = 1  # farthest in normal direction
    k = 1  # farthest in -edge direction (left)
    l = 1  # farthest in +edge direction (right)
    min_area = float('inf')
    best_rect = []
    for i in range(n):
        e = edge_vec(i)
        e_norm = normalize(e)
        # Normal perpendicular (outward)
        perp = (-e_norm[1], e_norm[0])
        # Advance j while cross product increases
        while True:
            next_j = (j+1)%n
            # Use distance to the line defined by e from hull[i]
            cur_d = abs((hull[j][0]-hull[i][0])*perp[0] + (hull[j][1]-hull[i][1])*perp[1])
            nxt_d = abs((hull[next_j][0]-hull[i][0])*perp[0] + (hull[next_j][1]-hull[i][1])*perp[1])
            if nxt_d <= cur_d:
                break
            j = next_j
        # Advance k (left extreme) using dot with -e
        while True:
            next_k = (k+1)%n
            cur_dot = dot((hull[k][0]-hull[i][0], hull[k][1]-hull[i][1]), e)
            nxt_dot = dot((hull[next_k][0]-hull[i][0], hull[next_k][1]-hull[i][1]), e)
            if nxt_dot >= cur_dot:  # moving away from hull[i] in e direction
                break
            k = next_k
        # Advance l (right extreme) using dot with +e
        while True:
            next_l = (l+1)%n
            cur_dot = dot((hull[l][0]-hull[i][0], hull[l][1]-hull[i][1]), e)
            nxt_dot = dot((hull[next_l][0]-hull[i][0], hull[next_l][1]-hull[i][1]), e)
            if nxt_dot <= cur_dot:
                break
            l = next_l
        # Compute rectangle dimensions
        height = abs((hull[j][0]-hull[i][0])*perp[0] + (hull[j][1]-hull[i][1])*perp[1])
        # Width = projection of hull onto e
        left_dot = dot((hull[k][0]-hull[i][0], hull[k][1]-hull[i][1]), e_norm)
        right_dot = dot((hull[l][0]-hull[i][0], hull[l][1]-hull[i][1]), e_norm)
        width = right_dot - left_dot
        area = width * height
        if area < min_area:
            min_area = area
            # Compute corners (not shown for brevity)
    return min_area

▶ Output

For a rectangle hull, returns the rectangle area (same as input).

Mental Model

Why one edge of the optimal rectangle coincides with a hull edge

If no hull edge aligns with the rectangle, you could rotate the rectangle slightly to reduce area — a classic optimisation theorem.

Proof by contradiction: if rectangle edge doesn't touch hull, you can shrink until it touches
If only vertices touch (no edge contact), you can rotate to reduce area
Thus at least one hull edge must be flush with the rectangle

📊 Production Insight

The three-pointer version requires careful management. The left/right extremes used dot product comparisons; make sure the direction of 'left' vs 'right' is consistent with the hull orientation (CCW). If the hull is clockwise, everything flips.

Numerical stability: when the edge length is very small, the normalisation can produce garbage. Skip very short edges (length < 1e-10) or ignore them.

Rule: always compute area using doubles and avoid sqrt until the final comparison of areas.

🎯 Key Takeaway

Minimum enclosing rectangle: one edge aligns with a hull edge. Use three antipodal pointers. O(n) after hull. Validate on a square first.

Implementation Pitfalls and Debugging Pattern

Rotating calipers looks simple on paper but bites you in subtle ways. The most common bugs: wrong while loop condition, off-by-one in pointer advancement, integer overflow in cross product (especially with large coordinates), and ignoring collinear hull points. Also, the algorithm requires a strictly convex hull in counterclockwise order — if your points are convex but in clockwise order, the antipodal relationship reverses.

A robust implementation should

Remove collinear points from hull (or handle them explicitly)
Use 64-bit integers for cross product when coordinates are integers
Limit the while loop to at most n steps to prevent infinite loops on degenerate hulls
Test on simple shapes: line, triangle, rectangle, regular hexagon
Validate against brute-force for small sets before trusting

The antipodal pointer j should never move backward — if it does, your cross product comparison is wrong or the hull is not convex.

⚠ Collinear points break everything

If your convex hull includes collinear points (e.g., points on edges), the cross product along an edge may be zero, causing the while loop to stop early or early-exit unexpectedly. Remove them during hull construction or prune them before rotating calipers.

📊 Production Insight

In production, you'll rarely write rotating calipers from scratch — you'll use a library like CGAL or Boost.Geometry. But when the library returns a wrong bounding box for a specific polygon, you need to debug. The most common failure is non-convex input (a wound polygon) — the algorithm silently returns garbage. Always assert convexity and CCW ordering at the entry point.

Another reality: floating-point precision can cause the cross product to not be strictly monotonic due to rounding errors. Use a small epsilon (1e-9) in the while loop to break ties.

Rule: validate convex hull before rotating calipers, and always wrap the hull in a convexity check.

🎯 Key Takeaway

Bug pattern: while loop condition, collinear points, integer overflow, hull orientation.

Always test on a rectangle. Add epsilon for floating point. Validate hull before call.

O(n) is only trustworthy after you've debugged the while loop thoroughly.

When rotating calipers fails

IfHull is not strictly convex

→

UsePrune collinear points. Use Graham scan with 'keep collinear' set to false.

IfHull is in clockwise order

→

UseReverse the list or re-run convex hull algorithm to get CCW order.

IfCross product comparison not monotonic due to floating precision

→

UseAdd epsilon tolerance. Consider using integer cross product if coordinates are integers.

IfWhile loop runs infinite

→

UseAdd a maximum iteration guard (n steps). If hit, hull likely has duplicate points or is degenerate.

🗂 Rotating Calipers vs Naive Approaches

Time complexity for common operations on convex polygons

Operation	Naive Approach	Rotating Calipers	Preprocessing Required
Diameter	O(n²)	O(n)	Convex hull O(n log n)
Minimum Width	O(n²)	O(n)	Convex hull O(n log n)
Closest pair between two hulls	O(nm)	O(n+m)	Convex hulls for each set
Minimum Enclosing Rectangle	O(n²)	O(n)	Convex hull O(n log n)
Collision detection (separating axis)	O(n²) per frame	O(n) per frame	Convex hull precomputed

🎯 Key Takeaways

Rotating calipers: O(n) scan of antipodal vertex pairs after O(n log n) convex hull. Reduces many O(n²) problems to O(n).
Each vertex is antipodal to O(1) others as we rotate 360° — the total antipodal pairs is O(n).
Applications: diameter, minimum width, minimum bounding rectangle, closest pair between hulls.
Always build convex hull first — rotating calipers only works on convex polygons.
Bug-prone areas: while loop condition (use >=), collinear hull points, integer overflow, hull orientation (must be CCW).
Test on simple shapes like rectangles and hexagons before deploying to production.

⚠ Common Mistakes to Avoid

✕Using > instead of >= in the while loop condition

Symptom

Diameter or width values are slightly smaller than the true value; for collinear edges, the antipodal pointer stops early, missing the correct pair.

Fix

Change the while condition to >=. Test on a rectangle where the correct diameter is the diagonal — if you get less than that, your comparison is strict.

✕Not removing collinear points from the convex hull

Symptom

The cross product along an edge with collinear vertices becomes zero, causing the while loop to not advance properly, leading to wrong antipodal assignments.

Fix

During hull construction (e.g., Graham scan), exclude points that lie on the line between two hull vertices. Alternatively, after hull construction, remove any vertex whose cross product with neighbours is zero.

✕Assuming hull is in CCW order when it's clockwise

Symptom

The cross product signs invert, causing the while loop to never advance j (since the cross product will never increase with the wrong orientation). The algorithm returns the diameter as the distance between adjacent points.

Fix

Compute the signed area of the hull. If it's positive, hull is CCW; if negative, reverse the hull list. In the algorithm, ensure the cross product function uses the correct orientation (o, a, b).

✕Integer overflow when using int for cross product with large coordinates

Symptom

Cross product wraps around to negative values, causing erratic pointer movement. This is subtle because it may only happen for large hulls or specific edge orientations.

Fix

Use 64-bit integers (long long in C++, long in Java) or switch to double. For coordinates up to 10^9, the cross product can exceed 2^63, so use BigInteger (Java) or Python's big ints.

✕Forgetting to wrap j when advancing beyond the last vertex

Symptom

Index out of bounds exception or, if the language allows it, accessing memory that's not a hull vertex, producing garbage distances.

Fix

Always use modulo n for j: j = (j + 1) % n. Also ensure the while loop doesn't wrap around more than n times — add a guard counter.

Interview Questions on This Topic

QWhat is an antipodal pair and why does rotating calipers only need to check O(n) pairs?Mid-levelReveal
An antipodal pair of a convex polygon consists of two vertices that have parallel supporting lines. As you rotate 360°, each vertex becomes antipodal to at most 2 other vertices (one for each adjacent edge). Thus, the total number of antipodal pairs is bounded by 2n, which is O(n). Rotating calipers exploits this by advancing a pointer j around the hull as edge (i, i+1) rotates, checking only the active antipodal pair per edge.
QHow would you find the minimum bounding rectangle of a point set using rotating calipers?SeniorReveal
First compute the convex hull of the point set (O(n log n)). Then apply rotating calipers with three antipodal pointers: one for the farthest point in the direction perpendicular to the current edge (height), and two for the extreme points in the direction parallel to the edge (left and right extents). For each hull edge, compute the area of the candidate rectangle (width * height) and keep the minimum. The rectangle's edge is collinear with the current hull edge. Total time O(n) after hull construction.
QWhat is the time complexity of rotating calipers and why can't it be better?JuniorReveal
The time complexity is O(n) after the convex hull is built. The loop iterates over n edges, and the inner while loop advances the antipodal pointer j at most n times total because j only moves clockwise and never resets. So the total steps are O(n). You cannot do better than linear because you need to examine each vertex at least once to determine the diameter or width — but you might reduce the constant factor. The preprocessing for the convex hull is O(n log n), which is optimal for sorting-based hull algorithms.
QHow would you handle a non-convex polygon with rotating calipers?Mid-levelReveal
Rotating calipers only works on convex polygons. For a non-convex polygon, you must first compute its convex hull (O(n log n)). The convex hull is the smallest convex polygon that contains all points. Many geometric properties of the original set (like diameter or bounding box) are determined by the hull's vertices. However, be aware that some properties (like minimum area enclosing rectangle) can be found using the convex hull and rotating calipers, but others (like the polygon's own width) are not the same as the hull's width. If you need the width of the non-convex polygon itself, you need a different algorithm.

Frequently Asked Questions

Does rotating calipers work on non-convex polygons?

No — rotating calipers requires a convex polygon. For non-convex polygons, compute the convex hull first (O(n log n)), then apply rotating calipers to the hull. The hull has at most n vertices, so the total complexity remains O(n log n).

What is the difference between diameter and width?

Diameter is the maximum distance between any two vertices of the convex hull (vertex-vertex). Width is the minimum distance between two parallel supporting lines that enclose the hull (edge-vertex). For a rectangle, diameter = diagonal, width = shorter side.

Why does the antipodal pointer only move forward?

As the edge (i, i+1) rotates, the antipodal vertex for that edge moves monotonically around the hull. Once j passes the antipodal position for edge i, it will never need to go back because the next edge i+1 has an antipodal vertex that is either the same or further ahead. This monotonic property guarantees O(n) total pointer movements.

Can rotating calipers handle integer coordinates?

Yes, but you must be careful with integer overflow in the cross product. For coordinates up to 10^9, the cross product can be up to 2*10^18, which fits in a 64-bit signed integer (9e18). But for larger coordinates, use Python's arbitrary-precision ints or double in other languages. Also, the final distance calculation requires floating point or rational arithmetic.

How do I get the actual points for the diameter pair, not just the distance?

Track the pair (i, j) or (i+1, j) that produced the maximum distance. In the loop, when you update max_dist, also store the corresponding vertex indices. For the other properties like bounding rectangle, you need to store the four corners computed from the edge and the three antipodal pointers.

🔥

Naren Founder & Author

Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.

About Naren Get in touch

Forged with 🔥 at TheCodeForge.io — Where Developers Are Forged