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:
“Words are finite organs of the infinite mind. They cannot cover the dimensions of what is in truth. They break, chop, and impoverish it.”
—Ralph Waldo Emerson (1803–1882)
“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)