Smallest enclosing box

In computational geometry, the smallest enclosing box problem is that of finding the box (hyperrectangle) of smallest measure (volume, area, perimeter, etc.) enclosing a given object or set of objects. It is a type of bounding volume.

It is sufficient to find the smallest enclosing box for the convex hull of the objects in question.

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.[1] It is possible to enumerate of the boxes of this kind in linear time with the approach called rotating calipers by Godfried Toussaint in 1983 [2] The same approact is applicable for finding the minimum-perimeter enclosing rectangle. [2]

See also

* Smallest enclosing ball

Minimum bounding box

References

1. ^ H. Freeman and R. Shapira, "Freeman Determining the Minimum-Area Encasing Rectangle for an Arbitrary Closed Curve", Comm. ACM, 1975, pp.409-413.

2. ^ a b Toussaint, G. T (1983). "Solving geometric problems with the rotating calipers". Proc. MELECON '83, Athens.