17.7 Rotating Calipers
After constructing a convex hull, many geometric questions remain: * What is the maximum distance between any two points?
17.7 Rotating Calipers
Problem
After constructing a convex hull, many geometric questions remain:
- What is the maximum distance between any two points?
- What is the width of the shape?
- Which pair of parallel supporting lines are farthest apart?
- What is the minimum bounding rectangle?
A naive approach often examines every pair of hull vertices.
For a hull containing h vertices:
O(h²)
comparisons may be required.
For large geometric datasets, this quickly becomes expensive.
Rotating calipers provide a powerful technique for transforming many quadratic geometric problems into linear scans over a convex polygon.
Solution
Imagine placing two parallel rulers against opposite sides of a convex polygon.
As one ruler rotates around the polygon boundary, the other ruler rotates with it. The pair remains parallel throughout the process.
Because a convex polygon is ordered geometrically, important geometric relationships evolve continuously as the rulers rotate.
Instead of examining every possible pair of vertices, the algorithm advances pointers around the hull while maintaining a geometric invariant.
This idea is known as the rotating calipers technique.
The method was introduced by entity["people","Godfried Toussaint","computational geometry researcher"] and has become one of the most useful tools in computational geometry.
Understanding Antipodal Pairs
The most common application is computing the diameter of a convex polygon.
The diameter is the largest distance between any two points on the hull.
Consider a convex polygon:
*
/ \\n * *
| |
* *
\ /
*
Two vertices are called an antipodal pair when parallel supporting lines can touch the polygon at those vertices simultaneously.
A surprising result is that the diameter must occur among the antipodal pairs.
Therefore, instead of testing every pair of vertices, we only need to examine a small subset.
Geometric Intuition
Imagine placing the polygon between two parallel walls.
Rotate the walls around the polygon.
Whenever one wall moves to the next edge, the opposite wall also moves forward but never moves backward.
This monotonic behavior is the key observation.
Because both pointers only move forward around the hull, the total work becomes linear.
Area-Based Advancement
Suppose the hull vertices are:
P0, P1, P2, ..., Ph−1
For a hull edge:
Pi → Pi+1
we search for the vertex on the opposite side that maximizes perpendicular distance.
Rather than computing distances directly, we compare triangle areas.
For edge:
Pi → Pi+1
and candidate vertices:
Pj
Pj+1
we compare:
area1 = abs(
orientation(
Pi,
Pi1,
Pj
)
)
area2 = abs(
orientation(
Pi,
Pi1,
Pj1
)
)
If:
area2 > area1
the opposite pointer advances.
The area of the triangle is proportional to the perpendicular distance from the edge.
This allows the algorithm to use the orientation predicate developed earlier in the chapter.
Diameter Algorithm
Assume the hull is stored in counterclockwise order.
def distance_squared(a, b):
dx = a.x - b.x
dy = a.y - b.y
return dx * dx + dy * dy
Rotating calipers for diameter:
def convex_diameter(hull):
n = len(hull)
if n <= 1:
return 0
j = 1
best = 0
for i in range(n):
ni = (i + 1) % n
while True:
nj = (j + 1) % n
current = abs(
orientation(
hull[i],
hull[ni],
hull[j]
)
)
next_area = abs(
orientation(
hull[i],
hull[ni],
hull[nj]
)
)
if next_area > current:
j = nj
else:
break
best = max(
best,
distance_squared(
hull[i],
hull[j]
)
)
return best
The algorithm returns the squared diameter.
A square root can be applied afterward if the actual distance is required.
Example
Consider the rectangle:
(0,0)
(8,0)
(8,3)
(0,3)
The diameter occurs between opposite corners:
(0,0)
(8,3)
or
(8,0)
(0,3)
Distance squared:
8² + 3²
=
73
The rotating calipers scan finds this result while examining only a linear number of antipodal pairs.
Why the Algorithm Is Linear
At first glance, the nested loops appear quadratic.
The key observation is that:
j never moves backward
Throughout the entire execution:
j
makes at most one complete revolution around the hull.
Therefore:
total pointer advances ≤ 2h
The inner loop contributes only linear work overall.
This is a common amortized-analysis pattern.
Width of a Convex Polygon
The same framework computes the width of a convex polygon.
Width is the minimum distance between two parallel supporting lines.
Visual representation:
==================
polygon
==================
As each hull edge becomes a supporting line, the opposite caliper identifies the farthest vertex from that edge.
The smallest such distance across all edges is the width.
Applications include:
- Manufacturing
- Object packing
- Computer vision
- Shape analysis
Minimum Bounding Rectangle
One of the most famous rotating-calipers applications is computing the minimum-area bounding rectangle.
Given a convex hull:
*
* *
* *
* *
*
find the rectangle of smallest area that completely contains it.
A brute-force search over all rectangle orientations would be expensive.
Rotating calipers exploit the fact that an optimal rectangle must align with one of the hull edges.
As the calipers rotate, candidate rectangles are updated incrementally.
The resulting algorithm runs in linear time after hull construction.
Maximum Distance Between Convex Polygons
Suppose two convex polygons are given.
Rotating calipers can determine:
maximum separation
minimum separation
tangents
by advancing pointers around both hulls simultaneously.
These techniques are important in collision detection and geometric optimization.
Convex Hull Requirement
Rotating calipers assume the input is convex.
For arbitrary point sets:
points
↓
convex hull
↓
rotating calipers
This pattern appears frequently.
The total complexity becomes:
O(n log n)
for hull construction plus:
O(h)
for the caliper scan.
Since:
h ≤ n
the hull construction dominates.
Numerical Considerations
The algorithm relies heavily on orientation predicates.
For integer coordinates:
orientation(a, b, c)
is exact.
For floating-point coordinates:
EPS = 1e-9
may be necessary when comparing areas.
Near-collinear hull edges can otherwise produce unstable behavior.
Robust geometry libraries often perform these comparisons using exact arithmetic.
Common Pitfalls
Applying to Non-Convex Input
Rotating calipers require a convex polygon.
Running the algorithm directly on arbitrary points produces incorrect results.
Forgetting Circular Indices
Hull traversal wraps around:
(i + 1) % n
Omitting modular arithmetic causes indexing errors.
Computing Square Roots Repeatedly
Diameter comparisons should use squared distances.
Square roots add cost without changing ordering.
Reinitializing the Opposite Pointer
The opposite pointer should continue from its previous position.
Resetting it for every edge destroys the linear-time guarantee.
Using Unordered Hull Vertices
The hull must be stored in cyclic order around the boundary.
Random vertex order invalidates the geometric assumptions.
Discussion
Rotating calipers are an excellent example of a geometric optimization technique that exploits structure rather than raw computation. Once a point set has been reduced to a convex hull, many seemingly quadratic problems collapse into linear scans. The algorithm works because convexity imposes strong ordering constraints: supporting lines advance monotonically, antipodal pairs evolve predictably, and pointers never need to backtrack.
This combination of geometric insight and amortized analysis makes rotating calipers one of the most elegant techniques in computational geometry. The next section extends the chapter from local geometric relationships to global geometric searches by introducing the closest-pair problem.