Mid-level 4 min · March 24, 2026

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

Q: 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).

Q: 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.

Q: 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.

Q: 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.

Q: 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.

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

Naren · Founder

Plain-English first. Then code. Then the interview question.

About

● Production Incident 🔎 Debug Guide

⚡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

Plain-English First

Imagine holding two parallel rulers (calipers) against opposite sides of a convex shape and rotating them 360 degrees together. At each angle, the distance between them gives the width of the shape in that direction. The maximum width is the diameter, the minimum is the smallest enclosing strip width. Rotating calipers formalize this: O(n) scan of antipodal vertex pairs.

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.pyPYTHON

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.pyPYTHON

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

Why width is not diameter

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.pyPYTHON

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.pyPYTHON

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).

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

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.

● Production incidentPOST-MORTEMseverity: high

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

Symptom

Bounding 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.

Assumption

The 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 cause

The 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.

Fix

Changed 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 guideSymptom → Action guide for the most common implementation bugs4 entries

Symptom · 01

Computed diameter is smaller than the actual farthest vertex distance

→

Fix

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.

Symptom · 02

Diameter value is erratic or changes with duplicate hull points

→

Fix

Ensure hull is strictly convex with no collinear interior points. Run a convex hull algorithm that excludes collinear vertices, or preprocess to remove them.

Symptom · 03

Bounding rectangle orientation is off by one edge

→

Fix

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.

Symptom · 04

Infinite loop in the while loop for degenerate hull

→

Fix

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.

★ Quick Reference: Rotating Calipers Debug CommandsOne-liners to isolate antipodal pair tracking issues in your implementation

While loop bound miss−

Immediate action

Print 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 now

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

Wrong diameter on rectangle+

Rotating Calipers vs Naive Approaches

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

5 patterns

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 PREP · PRACTICE MODE

Interview Questions on This Topic

Q01SENIOR

What is an antipodal pair and why does rotating calipers only need to ch...

Q02SENIOR

How would you find the minimum bounding rectangle of a point set using r...

Q03JUNIOR

What is the time complexity of rotating calipers and why can't it be bet...

Q04SENIOR

How would you handle a non-convex polygon with rotating calipers?

Q01 of 04SENIOR

What is an antipodal pair and why does rotating calipers only need to check O(n) pairs?

ANSWER

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.

FAQ · 5 QUESTIONS

Frequently Asked Questions

Does rotating calipers work on non-convex polygons?

What is the difference between diameter and width?

Why does the antipodal pointer only move forward?

Can rotating calipers handle integer coordinates?

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

🔥

That's Geometry. Mark it forged?

4 min read · try the examples if you haven't