Overview
Rotating calipers walks around a convex polygon while maintaining pairs of parallel support lines, testing antipodal vertex pairs that can define the polygon diameter.
CoreSource checked
Rotating Calipers Diameter
Finds the farthest pair of points on a convex polygon by scanning antipodal pairs.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Rotating Calipers
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
polygon diameterrotating calipersgeometric primitivesgeometry
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use after computing a convex hull when the farthest pair or diameter is needed.
- Use when the input polygon is convex and vertices are ordered.
When Not to Use
- Avoid on unsorted or nonconvex points unless a convex hull is computed first.
- Avoid when the distance metric is not Euclidean unless the method is adapted.
What It Does
- Rotating Calipers Diameter uses rotating parallel support lines over antipodal pairs for polygon diameter
- Organizes the work around polygon diameter and rotating calipers.
Use Cases
- Production and research workloads requiring rotating calipers via Finds the farthest pair of points on a convex polygon by scanning antipodal pairs.
- Rotating Calipers pipelines where O(n log n) time and O(n) space fit system constraints.
- Engineering comparisons against Rotating Calipers Width and Rotating Calipers Antipodal Pairs when tuning rotating calipers.
Inputs
- Points, segments, polygons, or geometric primitives
- Query or construction parameters
Outputs
- Geometric decision, measurement, or constructed structure
Pseudocode
- 1.Take convex hull vertices in cyclic order
- 2.Find an initial antipodal vertex
- 3.For each hull vertex i
- 4.Advance j while the next area is larger
- 5.Update the best distance for pair i,j
- 6.Return the farthest pair and distance
Canonical Example
- Input
- rectangle vertices (0,0), (3,0), (3,1), (0,1)
- Output
- diameter between opposite corners with distance sqrt(10)
- Explanation
- The antipodal scan tests corner pairs and finds the longest diagonal.
Implementation Notes
- Compute the convex hull before running calipers on a point set.
- Advance the opposite pointer while the triangle area increases.
- Track the maximum squared distance among tested antipodal pairs.
Common Pitfalls
- The method assumes convex hull order, not arbitrary point order.
- Parallel edges and equal area advances need careful tie handling.
- Squared distances are fine for comparison but should be reported consistently.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow rotating parallel support lines over antipodal pairs on a small polygon diameter example.
Step 1 of 6: Take convex hull vertices in cyclic order
geometry-mechanismNotes
Rotating calipers turns the diameter search on a convex polygon into a linear scan after hull construction.
Sources (3)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookComputational geometry textbook support for Rotating Calipers Diameter's geometric model, data structures, and robustness concerns.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Rotating Calipers Diameter's problem context, known alternatives, and practical selection tradeoffs.
Open sourceToussaint Rotating Calipers
PaperReference for rotating-calipers methods for polygon diameter, width, antipodal pairs, and related convex-polygon queries.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Conceptual neighborRotating Calipers
Geometry · Extended
Both use rotating calipers ideas for related polygon diameter problems.
Compare with thisRelationships
View full relationship pageConceptual neighborRotating Calipers Width
Both use rotating calipers ideas for related polygon diameter problems.
Conceptual neighborRotating Calipers Antipodal Pairs
Both use rotating calipers ideas for related polygon diameter problems.
Conceptual neighborRotating Calipers
Both use rotating calipers ideas for related polygon diameter problems.
Related Algorithms
Tags
GeometryComputational Geometry