otating 
alipers homepage
Some history:
In 1978, M.I. Shamos's Ph.D. thesis "Computational Geometry" marks the "birth" of the field within Computer Science. Among the results he presents is a very simple algorithm for finding the diameter of a convex polygon, i.e. the greatest distance determined a pair of points belonging to the polygon.
The diameter turns out to be determined by an anti-podal pair of points. Shamos provides a simple O(n) time algorithm for determining the anti-podal pairs of a convex n-gon. Since there are at most 3n/2 of these, the diameter can then be found in O(n) time.
As Toussaint later put it, Shamos' algorithm resembles rotating a pair of calipers around the polygon. Thus the term "Rotating Calipers". In 1983, Toussaint presents a paper in which a variety of problems are solved using the same technique. Since then, new algorithms based on the paradigm have been obtained, solving a multitude of problems.
They include:
- Computing distances
- Enclosing rectangles
- Triangulations
- Properties of convex polygons
- Thinnest transversals
Thesis
My Master's Thesis, Computational Geometry with the Rotating Calipers (in Postscript format) gathers the above problems, while providing details and proofs. The bibliography is available here for viewing.
Applet
To use the Rotating Calipers and solve many of the above problems yourself, go
to the Rotating Calipers applet page.
Back to my homepage
November 26th, 1999