Computational geometry with the rotating calipers
Hormoz. Pirzadeh · Library and Archives Canada (Government of Canada) · 1999
The Rotating Calipers is a paradigm used to solve a number of problems in the field of Computational Geometry. The original algorithm was presented by Shamos in 1978 in order to find the diameter of a convex polygon; a few years later, Toussaint showed that the essence of the algorithm can be used to solve a number of other problems. In the past twenty years, research done by Toussaint and others has shown the Rotating Calipers to be a paradigm in Computational Geometry, applicable to a variety of problems. The resulting algorithms are often optimal in their time complexity, and always efficient and easy to implement. This work is an extensive collection of these results, including all those obtained at McGill University. It is the first time such a collection has been done, and would therefore be viewed as an important asset by many researchers around the world. The results in question are reviewed, and proofs lacking in their original articles are provided. Furthermore, a new result is obtained. The problems studied in this work include the diameter and width of convex polygons, the maximum and minimum distance between convex polygons, the minimum area and minimum perimeter enclosing rectangles for convex polygons, onion and spiral triangulations, quadrangulations, merging convex hulls, intersecting convex polygons, common tangents and critical support lines, and vector sums of convex polygons. To supplement the theoretical aspect of this work, a synthesis of this work is provided on the Internet, as well as an interactive applet demonstrating the use of the Rotating Calipers in solving many of the above mentioned problems.