In computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

, the smallest enclosing box problem is that of finding the oriented minimum bounding box enclosing a set of points. It is a type of bounding volume

Bounding volume

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex...

. "Smallest" may refer to volume

Volume

Volume is the quantity of three-dimensional space enclosed by some closed boundary, for example, the space that a substance or shape occupies or contains....

, area

Area

Area is a quantity that expresses the extent of a two-dimensional surface or shape in the plane. Area can be understood as the amount of material with a given thickness that would be necessary to fashion a model of the shape, or the amount of paint necessary to cover the surface with a single coat...

, perimeter

Perimeter

A perimeter is a path that surrounds an area. The word comes from the Greek peri and meter . The term may be used either for the path or its length - it can be thought of as the length of the outline of a shape. The perimeter of a circular area is called circumference.- Practical uses :Calculating...

, etc. of the box.

It is sufficient to find the smallest enclosing box for the convex hull

Convex hull

In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....

 of the objects in question. It is straightforward to find the smallest enclosing box that has sides parallel to the coordinate axes; the difficult part of the problem is to determine the orientation of the box.

Two dimensions

For the convex polygon

Convex polygon

In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...

, 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

Rotating calipers

In computational geometry, rotating calipers is a method used to construct efficient algorithms for a number of problems.The method was first used by Michael Shamos in 1978 for determining all antipodal pairs of points and vertices on a convex polygon....

 by
Godfried Toussaint

Godfried Toussaint

Godfried T. Toussaint is a Research Professor of Computer Science at New York University Abu Dhabi in Abu Dhabi, United Arab Emirates. He is an expert on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition , motion planning, visualization ,...

 in 1983. The same approach is applicable for finding the minimum-perimeter enclosing rectangle.

Three dimensions

In 1985, Joseph O'Rourke

Joseph O'Rourke (professor)

Joseph O'Rourke is the Olin Professor of Computer Science at Smith College and the chair of the Smith computer science department. His main research interest is computational geometry....

 published a cubic-time algorithm to find the minimum-volume enclosing box of a 3-dimensional point set. O'Rourke's approach uses a 3-dimensional rotating calipers technique. This algorithm has not been improved on as of August 2008, although heuristic methods for tackling the same problem have been developed.

Preparatory theorems in O'Rourke's work were proved to the effect that:

• There must exist two neighbouring faces of the smallest-volume enclosing box which both contain an edge of the convex hull of the point set. This criterion is satisfied by a single convex hull edge collinear with an edge of the box, or by two distinct hull edges lying in adjacent box faces.
• The other four faces need only contain a point of the convex hull. Again, the points which they contain need not be distinct: a single hull point lying in the corner of the box already satisfies three of these four criteria.

It follows in the most general case where no convex hull vertices lie in edges of the minimal enclosing box, that at least 8 convex hull points must lie within faces of the box: two endpoints of each of the two edges, and four more points, one for each of the remaining four box faces. Conversely, if the convex hull consists of 7 or fewer vertices, at least one of them must lie within an edge of the hull's minimal enclosing box.
The minimal enclosing box of the regular tetrahedron is a cube, with side length 1/√2 that of the tetrahedron; for instance, a regular tetrahedron with side length √2 fits into a unit cube

Unit cube

A unit cube, sometimes called a cube of side 1, is a cube whose sides are 1 unit long. The volume of a 3-dimensional unit cube is 1 cubic unit, and its total surface area is 6 square units.- Unit Hypercube :...

, with the tetrahedron's vertices lying at the vertices (0,0,0), (0,1,1), (1,0,1) and (0,1,1) of the unit cube.