Subject 2.09: How can I find the minimum area rectangle enclosing a set of points?
First take the convex hull of the points. Let the resulting convex polygon be P. It has been known for some time that the minimum area rectangle enclosing P must have one rectangle side flush with (i.e., collinear with and overlapping) one edge of P. This geometric fact was used by Godfried Toussaint to develop the “rotating calipers” algorithm in a hard-to-find 1983 paper, “Solving Geometric Problems with the Rotating Calipers” (Proc. IEEE MELECON). The algorithm rotates a surrounding rectangle from one flush edge to the next, keeping track of the minimum area for each edge. It achieves O(n) time (after hull computation). See the “Rotating Calipers Homepage” http://www.cs.mcgill.ca/~orm/rotcal.frame.html for a description and applet.
