Rotating calipers


In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.
The method is so named because the idea is analogous to rotating a spring-loaded vernier caliper around the outside of a convex polygon. Every time one blade of the caliper lies flat against an edge of the polygon, it forms an antipodal pair with the point or edge touching the opposite blade. The complete "rotation" of the caliper around the polygon detects all antipodal pairs; the set of all pairs, viewed as a graph, forms a thrackle. The method of rotating calipers can be interpreted as the projective dual of a sweep line algorithm in which the sweep is across slopes of lines rather than across - or -coordinates of points.

History

The rotating calipers method was first used in the dissertation of Michael Shamos in 1978. Shamos uses this method to generate all antipodal pairs of points on a convex polygon and to compute the diameter of a convex polygon in time. Godfried Toussaint coined the phrase "rotating calipers" and also demonstrated that the method was applicable in solving many other computational geometry problems.

Shamos's algorithm

Shamos gave following algorithm in his dissertation for the rotating calipers method that generated all antipodal pairs of vertices on convex polygon:

/* p is in standard form, ie, counter clockwise order,
distinct vertices, no collinear vertices.
ANGLE is a procedure that returns the clockwise angle
swept out by a ray as it rotates from a position parallel
to the directed segment Pm,Pm+1 to a position parallel to Pn,Pn+1
We assume all indices are reduced to mod N.
GetAllAntiPodalPairs
//Find first anti-podal pair by locating vertex opposite P1
i = 1
j = 2
while angle < pi
j++
yield i,j
/* Now proceed around the polygon taking account of
possibly parallel edges. Line L passes through
Pi, Pi+1 and M passes through Pj, Pj+1
*/
//Loop on j until all of P has been scanned
current = i
while j != n
if angle <= angle
j++
current = j
else
i++
current = i
yield i,j
//Now take care of parallel edges
if angle = angle
yield i+1, j
yield i, j+1
yield i+1, j+1
if current = i
j++
else
i++

Another version of this algorithm appeared in the text by Preparata and Shamos in 1985 that avoided calculation of angles:

GetAllAntiPodalPairs
i0 = n
i = 1
j = i+1
while > Area)
j = j+1
j0 = j
while
i = i+1
yield i,j
while > Area
j=j+1
if != )
yield i,j
else
return
if = Area)
if != )
yield i,j+1
else
yield i+1,j

Applications

Pirzadeh describes various applications of rotating calipers method.

Distances