Rotating calipers
The rotating calipers method is an algorithmic paradigm in computational geometry for efficiently solving optimization problems on convex polygons, such as computing the diameter (the maximum distance between any two points on the boundary) or the minimum width, by maintaining and rotating pairs of parallel supporting lines—analogous to physical calipers—to identify antipodal vertex pairs in linear time relative to the number of vertices.[1] Introduced by Michael Ian Shamos in his 1978 doctoral thesis, the technique leverages the convexity of the input polygon to ensure that supporting lines rotate in a monotonic fashion, advancing only at vertices and requiring O(n operations to enumerate all antipodal pairs, where n is the number of vertices.[1] This approach builds on the convex hull, as the extremal points for such problems lie on the hull, and it avoids exhaustive pairwise distance computations that would take quadratic time.[1] Godfried Toussaint's 1983 generalization extended the method beyond a single pair of calipers, allowing multiple sets to operate simultaneously on one polygon or across multiple polygons, enabling O(n) solutions to a broader class of problems including the minimum-area enclosing rectangle, the maximum distance between two convex polygons, the vector sum of polygons, and the merging of convex hulls.[2] For instance, in finding the smallest enclosing rectangle, the calipers rotate to align with polygon edges, testing orientations only at critical angles defined by the vertices.[2] The method's efficiency stems from its incremental nature: after initializing the calipers at an initial antipodal pair (e.g., the leftmost and rightmost vertices), rotation proceeds by advancing the caliper on the side where the supporting line's direction changes, ensuring each vertex is processed a constant number of times.[1] Applications extend to practical domains such as pattern recognition (e.g., linear separability of point sets), robotics (e.g., collision avoidance via critical support lines), and facility location (e.g., farthest-point Voronoi diagrams), where the technique's simplicity and optimality make it a foundational tool.[2]Fundamentals
Definition and Principle
The rotating calipers method is a computational geometry technique that simulates the physical process of using adjustable calipers to measure features of a convex shape by rotating a pair of parallel supporting lines around its boundary.[2] These lines, analogous to the jaws of physical calipers, remain in contact with the convex hull at its vertices while rotating, allowing the identification of extremal geometric properties such as maximum distances or widths.[3] The core analogy draws from tightening calipers around a physical object and slowly rotating them to maintain tight contact, which in the algorithmic context translates to dynamically adjusting the orientation of the parallel lines to stay tangent to the hull's edges and vertices.[2] This method fundamentally relies on the convexity of the polygon, ensuring that the supporting lines touch the boundary at vertices or along edges, and that the polygon lies entirely on one side of each line during rotation.[2] For a convex hull with n vertices ordered clockwise, the lines start in an initial position, such as aligned with one edge of the hull, and rotate synchronously while tracking contact points.[3] As rotation proceeds, the lines pivot only at discrete events—specifically, when a contact point advances from one vertex to the next—leveraging the convex structure to avoid continuous adjustment and enabling efficient computation.[2] The algorithm achieves linear time complexity, O(n), by advancing caliper pointers (representing the contact vertices) a total of at most $3n times across a full rotation, as each vertex is visited a bounded number of times without backtracking.[2] This discrete event-driven approach processes the hull in a single pass, computing extremal features like antipodal vertex pairs where the supporting lines are parallel.[2]Antipodal Pairs
In the context of the rotating calipers method applied to a convex polygon, an antipodal pair consists of two features (vertices or edges) such that there are parallel supporting lines touching the polygon at each feature, with the polygon lying entirely on one side of each line.[1] These pairs represent configurations where the supporting lines achieve local extrema for problems like diameter or width computation.[2] Antipodal pairs are classified into three main types: vertex-vertex pairs, where both are vertices; vertex-edge pairs (including edge-vertex), where one is a vertex and the other is an edge; and edge-edge pairs, where both are edges of the polygon.[4] For a convex polygon with n vertices, the total number of such pairs is bounded by O(n), ensuring that enumeration remains efficient.[2] During the rotation process of the calipers—parallel supporting lines that rotate around the polygon—events occur at discrete moments when a caliper reaches the next vertex, signaling that the current antipodal pair is no longer valid and must advance.[4] These events are determined by comparing the angular displacements required for each caliper to align with the subsequent edge, advancing the one with the smaller angle.[2] A key mathematical property of antipodal pairs in a convex polygon is that they form a cyclic sequence, where traversing from one pair to the next follows the boundary without backtracking, allowing the full set to be enumerated in linear time O(n) over a single 360-degree rotation.[1] This cyclicity arises from the convexity, ensuring that the supporting lines maintain consistent orientation relative to the polygon's boundary as they rotate.[4]Historical Development
Origins with Shamos
The rotating calipers method was introduced by Michael Ian Shamos in his 1978 PhD thesis at Yale University, completed in May 1978, as part of broader efforts to develop efficient algorithms in computational geometry.[1] This innovation emerged within the context of constructing and analyzing convex hulls for finite point sets in the plane, where Shamos sought to optimize solutions for fundamental geometric queries.[5] The thesis built on prior techniques like Graham's scan for convex hull computation, emphasizing linear-time operations for problems on already convex structures. The original motivation centered on computing the diameter of a convex polygon—the maximum distance between any two vertices—achieving an O(n time complexity for an n-vertex polygon, a significant improvement over the O(n^2) time required for naive pairwise checks on general point sets (after O(n log n) convex hull construction).[1] Prior approaches often relied on exhaustive evaluations or suboptimal sorting, but Shamos's method leveraged the convexity property to avoid such overhead.[6] By assuming the input polygon was convex (or precomputing the hull in O(n log n) time), the algorithm enabled linear-time resolution of the diameter problem.[7] The key innovation involved simulating the rotation of two parallel supporting lines (analogous to caliper jaws) around the polygon's boundary to systematically identify all antipodal vertex pairs—points where the lines touch the hull in opposite directions—without performing O(n²) exhaustive comparisons.[1] This process generates O(n) such pairs in O(n) time, allowing the diameter to be selected as the maximum distance among them.[8] The rotation advances by monitoring changes in supporting line orientations relative to polygon edges and vertices. An early limitation of Shamos's formulation was its dependence on explicit angle computations to determine rotation directions and antipodal transitions, which could introduce numerical precision issues in implementations relying on floating-point trigonometry.[1] Despite this, the method established a foundational paradigm for linear-time geometric optimizations on convex shapes.[9]Expansions by Toussaint
Godfried Toussaint played a pivotal role in popularizing and expanding the rotating calipers technique, formally coining the term in his 1983 paper where he demonstrated its versatility beyond the original diameter computation introduced by Shamos.[2] In this seminal work, Toussaint applied the method to compute the minimum width of a convex polygon—defined as the smallest distance between parallel supporting lines—and the smallest-area enclosing rectangle, both achievable in linear time by rotating calipers through antipodal pairs.[2] He further extended it to polygon distances, notably the maximum separation between two convex polygons, by employing dual sets of calipers to track supporting lines across both shapes simultaneously.[2] Collaborations and influences soon followed, with Franco P. Preparata and Michael I. Shamos presenting an angle-free variant in their 1985 textbook, which refined the rotation mechanism using vector comparisons to avoid trigonometric computations, enhancing numerical stability. This work built directly on Toussaint's framework, influencing subsequent developments like David Kirkpatrick and Raimund Seidel's output-sensitive algorithms for shape enclosures, where rotating calipers informed prune-and-search strategies for optimal bounding structures. By the 1990s, the technique had evolved from single-polygon metrics to multi-object operations, incorporating Toussaint's early ideas on vector sums and polygon merging to handle interactions between multiple geometric entities in linear time.[2]Core Algorithms
Shamos's Method
Shamos's method, introduced in his 1978 PhD thesis, provides an O(n time algorithm for computing the diameter of a convex polygon by systematically enumerating all antipodal vertex pairs using rotating parallel supporting lines, analogous to physical calipers rotating around the polygon.[1] However, the original angle-based implementation had flaws, such as using clockwise angles, which could miss pairs; these were addressed in later refinements. The core idea involves maintaining two parallel supporting lines that touch the polygon at vertices p_i and p_j, initially positioned such that they are parallel to one edge of the polygon, and then rotating them incrementally to capture all configurations where the lines remain supporting.[1] The algorithm begins with initialization in O(n) time: select an initial direction, such as horizontal, to find the first antipodal pair p_i and p_j by scanning the vertices to identify those with extremal projections in that direction.[1] Once initialized, the process enters a loop that simulates rotation by advancing the calipers to the next event, where an event occurs when one supporting line slips off its current vertex and aligns with the adjacent edge. For current vertices p_i and p_j, compute the outward angles \theta_i between the current supporting line and the edge p_i p_{i+1}, and \theta_j between the supporting line and the edge p_j p_{j+1}.[1] The rotation decision relies on comparing these angles: if \theta_j < \theta_i, advance the caliper at p_j by rotating the supporting lines by \theta_j, updating the pair to p_{j+1} and p_i; conversely, if \theta_i < \theta_j, advance at p_i to form p_{i+1} and p_j.[1] In the case of equality \theta_i = \theta_j (indicating parallel next edges), both calipers advance simultaneously, generating up to three additional antipodal pairs: one with each advanced vertex and the fully advanced pair.[9] This comparison effectively selects the caliper that first loses contact with its vertex, equivalent to argmax over the direction vectors of the next edges relative to the current supporting direction.[1] Event handling ensures progress without redundancy: each advancement updates the pointers i and j in constant time, and the loop continues until the initial configuration is revisited after processing all vertices, typically generating O(n antipodal pairs in total, at most 2n.[10] The following pseudocode outlines the procedure, assuming the polygon vertices are ordered counterclockwise and indices wrap around modulo n. Note that the current pair is recorded at the start of each iteration before computing angles (not shown explicitly here for brevity):This structure guarantees each of the O(n) events is handled in O(1) time, yielding overall O(n) complexity, and all antipodal pairs are found without repetition by monotonically advancing the pointers around the boundary.[1]Input: [Convex polygon](/page/Convex_polygon) P with n vertices p_1, ..., p_n Output: All antipodal pairs (and optionally the [diameter](/page/Diameter)) 1. Find initial antipodal pair (p_i, p_j) for horizontal direction ([O(n](/page/O(n)) scan) 2. Record initial pair (p_i, p_j) 3. Set current_direction to horizontal 4. While true: a. Compute θ_i = [angle](/page/Angle) between current_direction and [vector](/page/Vector)(p_i, p_{i+1}) b. Compute θ_j = [angle](/page/Angle) between current_direction and [vector](/page/Vector)(p_j, p_{j+1}) c. If θ_i == θ_j: - Record additional pairs: (p_i, p_{j+1}), (p_{i+1}, p_j), (p_{i+1}, p_{j+1}) if distinct - Advance i to i+1, j to j+1 - Update current_direction by θ_i d. Else if θ_i < θ_j: - Advance i to i+1 - Update current_direction by θ_i e. Else: - Advance j to j+1 - Update current_direction by θ_j f. Record the new current pair (after advance) g. If back to initial (i, j) and direction, break 5. (Optional: Among recorded pairs, select max distance for [diameter](/page/Diameter))Input: [Convex polygon](/page/Convex_polygon) P with n vertices p_1, ..., p_n Output: All antipodal pairs (and optionally the [diameter](/page/Diameter)) 1. Find initial antipodal pair (p_i, p_j) for horizontal direction ([O(n](/page/O(n)) scan) 2. Record initial pair (p_i, p_j) 3. Set current_direction to horizontal 4. While true: a. Compute θ_i = [angle](/page/Angle) between current_direction and [vector](/page/Vector)(p_i, p_{i+1}) b. Compute θ_j = [angle](/page/Angle) between current_direction and [vector](/page/Vector)(p_j, p_{j+1}) c. If θ_i == θ_j: - Record additional pairs: (p_i, p_{j+1}), (p_{i+1}, p_j), (p_{i+1}, p_{j+1}) if distinct - Advance i to i+1, j to j+1 - Update current_direction by θ_i d. Else if θ_i < θ_j: - Advance i to i+1 - Update current_direction by θ_i e. Else: - Advance j to j+1 - Update current_direction by θ_j f. Record the new current pair (after advance) g. If back to initial (i, j) and direction, break 5. (Optional: Among recorded pairs, select max distance for [diameter](/page/Diameter))
Preparata-Shamos Variant
In 1985, Franco P. Preparata and Michael I. Shamos proposed a refined version of the rotating calipers algorithm that replaces trigonometric computations with cross-product operations to determine when to advance the calipers, enhancing numerical stability and practical efficiency.[11] This variant builds on Shamos's original angle-based method by using vector cross products to compare orientations without invoking functions like \atan2 or \cos/\sin. It addresses the flaws in the original angle computations. The core decision mechanism involves checking the orientation at a caliper position p_i relative to the opposite caliper at p_j. Specifically, compute the sign of the cross product (p_{i+1} - p_i) \times (p_j - p_i); a positive value indicates that the caliper at p_i should advance to p_{i+1}, as p_j lies to the left of the directed edge from p_i to p_{i+1}. This cross product, equivalent to twice the signed area of the triangle formed by the points, provides a direct geometric test for antipodal pair progression. The primary advantages include avoidance of floating-point precision issues inherent in angular computations, which can accumulate errors in iterative rotations, while preserving the overall O(n) time complexity for convex polygons with n vertices. Implementation is straightforward and compatible with standard convex hull outputs, such as those from the Graham scan (which sorts points by polar angle) or Jarvis march (gift-wrapping), allowing seamless integration into broader geometric pipelines. A key limitation is the assumption of a convex input polygon; for non-convex polygons, a preprocessing step to compute the convex hull is required, adding O(n \log n) time in the worst case using algorithms like Graham scan.Applications
Polygon Diameters and Widths
The rotating calipers method enables the efficient computation of the diameter of a convex polygon, defined as the maximum distance between any two points on its boundary. This extremal distance is achieved by evaluating the Euclidean distance \|p - q\| for each pair of vertices p and q that form antipodal pairs during the caliper rotation process. The diameter d is thus given byd = \max \| p_i - p_j \|
where the maximum is taken over all antipodal vertex pairs (i, j).[2] This approach, originally proposed by Shamos, runs in O(n) time for an n-vertex polygon by generating all antipodal pairs in linear time and checking distances only at these critical configurations.[2] Due to the convexity of the polygon, all local maxima of pairwise distances occur at antipodal pairs, as the supporting lines at these points are parallel and the distance function between them is maximized there; a proof relies on the fact that for non-antipodal points, moving along the boundary can only increase the separation until an antipodal configuration is reached.[2] For example, in a regular n-gon, the diameter corresponds to the distance between opposite vertices (or the closest approximation for odd n), and the rotating calipers algorithm verifies this by rotating through the antipodal pairs in O(n) time.[12] The minimum width of a convex polygon, defined as the smallest distance between any pair of parallel supporting lines that sandwich the polygon, is similarly computed using rotating calipers by tracking the perpendicular distance between the caliper lines as they rotate. This minimum width w is
w = \min (\text{distance between caliper lines})
over all orientations, with the minimum occurring at antipodal pairs that may involve vertex-edge contacts. The algorithm identifies these by advancing the calipers to successive antipodal configurations and computing the projection of the polygon onto the direction perpendicular to the lines, achieving O(n) time overall. Convexity ensures that the global minimum width is attained at such pairs, as intermediate orientations yield larger separations.[12]