- 1 -Solving Geometric Problems with the Rotating Calipers *Godfried ToussaintSchool of Computer ScienceMcGill UniversityMontreal, Quebec, CanadaABSTRACTShamos [1] recently showed that the diameter of a convex n-sided polygon could becomputed in O(n) time using a very elegant and simple procedure which resemblesrotating a set of calipers around the polygon once. In this paper we show that this sim-ple idea can be generalized in two ways: several sets of calipers can be used simulta-neously on one convex polygon, or one set of calipers can be used on several convexpolygons simultaneously. We then show that these generalizations allow us to obtainsimple O(n) algorithms for solving a variety of problems defined on convex polygons.Such problems include (1) finding the minimum-area rectangle enclosing a polygon,(2) computing the maximum distance between two polygons, (3) performing the vec-tor-sum of two polygons, (4) merging polygons in a convex hull finding algorithms,and (5) finding the critical support lines between two polygons. Finding the criticalsupport lines, in turn, leads to obtaining solutions to several additional problems con-cerned with visibility, collision, avoidance, range fitting, linear separability, and com-puting the Grenander distance between sets.1. IntroductionLet P = (p1, p2,..., pn) be a convex polygon with n vertices in standard form, i.e., the verticesare specified according to cartesian coordinates in a clockwise order and no three consecutive ver-tices are colinear. We assume the reader is familiar with [1]. In [1] Shamos presents a very simplealgorithm for computing the diameter of P. The diameter is the greatest distance between parallellines of support of P. A line L is a line of support of P if the interior of P lies completely to one sideof L. We assume here that L is directed such that P lies to the right of L. Figure 1 illustrates twoparallel lines of support. A pair of vertices pi, pj is an antipodal pair if it admits parallel lines ofsupport. The algorithm of Shamos [1] generates all O(n) antipodal pairs of vertices and selects thepair with largest distance as the diameter-pair. The procedure resembles rotating a pair of dynam-ically adjustable calipers once around the polygon. Consider Figure 1. To initialize the algorithma direction such as the x-axis is chosen and the two antipodal vertices pi and pj can be found in O(n)time. To generate the next antipodal pair we consider the angles that the lines of support at pi andpj make with edges pipi+1 and pjpj+1, respectively. Let angle θj < θi. Then we “rotate” the lines ofsupport by an angle θj, and pj+1, pi becomes the next antipodal pair. This process is continued untilwe come full circle to the starting position. In the event that θj = θi three new antipodal pairs aregenerated.* Published in Proceedings of IEEE MELECON’83, Athens, Greece, May 1983.- 2 -In this paper we show that this simple idea can be generalized in two ways: several sets ofcalipers can be used on one polygon or one pair of calipers can be used on several polygons. Wethen show that these generalizations provide simple O(n) solutions to a variety of geometricalproblems defined on convex polygons. Such problems include the minimum-area enclosing rect-angle, the maximum distance between sets, the vector sum of two convex polygons, merging con-vex polygons, and finding the critical support lines of linearly separable sets. The last problem, inturn, has applications to problems concerning visibility, collision avoidance, range fitting, linearseparability, and computing the Grenander distance between sets.2. The Smallest-Area Enclosing RectangleThis problem has received attention recently in the image processing literature and has appli-cations in certain packing and optimal layout problems [2] as well as automatic tariffing in goods-traffic [3]. Freeman and Shapira [2] prove the following crucial theorem for solving this problemTheorem 2.1: The rectangle of minimum area enclosing a convex polygon has a side collinearwith one of the edges of the polygon.The algorithm presented in [2] constructs a rectangle in O(n) time for each edge of P and se-lects the smallest of these for a total running time of O(n2).This problem can be solved in O(n) time using two pairs of calipers orthogonal to each other.Let Ls(pi) denote the directed line of support of the polygon at vertex pi such that P is to the rightof the line. Let L(pi, pj) denote the line through pi and pj. The first step consists of finding the ver-tices with the minimum and maximum x and y coordinates. Let these vertices be denoted by pi, pk,pl, and pj, respectively, and refer to Figure 2. We next construct Ls(pj) and Ls(pl) as the first set ofcalipers in the x direction, and Ls(pi), Ls(pk) as the second set of calipers in a direction orthogonalFig. 1pipi+1pjpi+2pj+1pj+2θiθjpipjθlθjpkplθkθiFig. 2- 3 -to that of the first set. All this can be done in O(n) time. As in Shamos’ diameter algorithm we nowhave four, instead of two, angles to consider θi, θj, θk and θl. Let θi = min{θi, θj, θk,θl}. We “ro-tate” the four lines of support by an angle θi, L(pi,pi+1) forms the base line of the rectangle associ-ated with edge pipi+1 and the corners of the rectangle can be computed easily in O(1) time from thecoordinates of pi, pi+1, pj, pk and pl. We now have a new set of angles and the procedure is repeateduntil we scan the entire polygon. The area of each rectangle can be computed in constant time inthis way resulting in a total running time of O(n). Another O(n) algorithm that implements this ideausing a data structure known as a star is described in [4].3. The Maximum Distance Between Two Convex PolygonsLet P = (p1, p2,..., pn) and Q = (q1, q2,..., qn) be two convex polygons. The maximum distancebetween P and Q, denoted by dmax(P,Q), is defined asdmax(P,Q) = {d(pi, qj)} i,j = 1, 2,..., n,where d(pi, qj) is the euclidean distance between pi and qj. This distance measure has applicationsin cluster analysis [5]. A rather complicated O(n) algorithm for this problem appears in [6]. How-ever, a very simple solution can be obtained by using a pair of calipers as in Figure 3. In Figure 3the parallel lines of support Ls(qj) and Ls(pi) have opposite directions and thus pi and qjare an an-tipodal pair between the sets P and Q. The two lines of support define two angles θi and φj, andthe algorithm proceeds as in the diameter problem of Shamos [1]. Note that