Minimum bounding rectangle

The surrounding minimal rectangle (MUR ) (English: minimum bounding rectangle, MBR, also bounding box and envelope ) denotes the smallest axis-aligned rectangle that encloses a given set of objects. Although the term apparently implies a two-dimensional, so one speaks also in other dimensions of a minimal surrounding ( hyper) rectangle.

Mathematically, it is a very simple closure operator on n-dimensional intervals ( blocks ).

The term comes from the computer science and finds application for example in data storage in index structures (especially in the R- tree), in the approximation of complex objects such as polygons and in computer graphics (see bounding volume ) and in geographic information systems, as for computer rectangles faster to process than are complex objects.

While in computer graphics also rotated rectangles can occur as a "bounding box", only axis-aligned cuboids are admitted as MBR in general.

Representation of a minimal bounding rectangle

A minimum bounding rectangle can be represented by the minimum and maximum in each dimension. These values ​​can be interpreted and stored as two vectors, a minimum and a maximum vector vector. If one interprets these two vectors geometrically, they are two opposite corners of the MURs. We say also that these two items the MUR " span ".

Mathematically for a MUR for all objects and dimensions:

With the largest and the smallest vector with this property are, so there's no smaller rectangle with this property.

Extensivity and monotonicity

As a closure operator MUR have important properties for use in algorithms. Of particular importance are the extensivity and monotonicity

In search trees such as the R- tree, they are used to increase efficiency. This allows the extensivity to exclude whole subtrees when searching using the MUR of the subtree. The monotony allows to estimate also request areas by means of its MUR.

If objects are given, then applies

The exact MUR an object can therefore alone be calculated using the MURs of sub- objects.

Approximation using minimal bounding rectangle

Extended objects like polygons can be stored approximated by their MUR. The advantage of using MURs over, for example the convex hull of an object is the much lower memory overhead and the faster computation of overlaps. These benefits are paid for with a low accuracy of the approximation. Predominate in particular geographic data such as maps here but clearly the advantages.

• Data structure
• Geometry
• Geoinformatics