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:
“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)
“The truth is that a Pigmy and a Patagonian, a Mouse and a Mammoth, derive their dimensions from the same nutritive juices.... [A]ll the manna of heaven would never raise the Mouse to the bulk of the Mammoth.”
—Thomas Jefferson (1743–1826)