Two Dimensions
For the convex polygon, a linear time algorithm for the minimum-area enclosing rectangle is known. It is based on the observation that a side of a minimum-area enclosing box must be collinear with a side of the convex polygon. It is possible to enumerate boxes of this kind in linear time with the approach called rotating calipers by Godfried Toussaint in 1983. The same approach is applicable for finding the minimum-perimeter enclosing rectangle.
Read more about this topic: Minimum Bounding Box Algorithms
Famous quotes containing the word dimensions:
“Why is it that many contemporary male thinkers, especially men of color, repudiate the imperialist legacy of Columbus but affirm dimensions of that legacy by their refusal to repudiate patriarchy?”
—bell hooks (b. c. 1955)
“I was surprised by Joe’s asking me how far it was to the Moosehorn. He was pretty well acquainted with this stream, but he had noticed that I was curious about distances, and had several maps. He and Indians generally, with whom I have talked, are not able to describe dimensions or distances in our measures with any accuracy. He could tell, perhaps, at what time we should arrive, but not how far it was.”
—Henry David Thoreau (1817–1862)