Minimally surrounding rectangle

MUR multiple polygons

A three-dimensional body and a minimally surrounding cuboid (in white; rotates)

The minimally surrounding rectangle (MUR) (English: minimum bounding rectangle , MBR, also bounding box and envelope ) describes the smallest possible axially parallel rectangle that encloses a given number of objects. Even if the term apparently implies a two-dimensionality, one speaks of a minimally surrounding (hyper) rectangle in other dimensions as well .

Mathematically, it is a very simple hull operator . For this you have to allow the entire plane as a borderline case of a rectangle.

The term comes from computer science and is used there, among other things, for data storage in index structures (especially in the R-tree ), for the approximation of complex objects such as polygons and in computer graphics (see bounding volume ) and in geographic information systems , as rectangles for computers can be processed faster than complex objects.

While rotated rectangles can also appear as “bounding boxes” in computer graphics, generally only parallel-axis cuboids are permitted as MBR.

Representation of a minimally surrounding rectangle

A minimally surrounding rectangle can be represented by the minimum and maximum in each individual dimension. These values ​​can be interpreted and stored as two vectors, a minimum vector and a maximum vector. If one interprets these two vectors geometrically, they are two opposite corners of the MUR. It is also said that these two points “open up” the MUR.

Thus, in the two-dimensional case, these are four values: , , , or the two tuple (lower left corner) and (upper right corner). ${\displaystyle \textstyle \min _{x}}$ ${\displaystyle \textstyle \min _{y}}$ ${\displaystyle \textstyle \max _{x}}$ ${\displaystyle \textstyle \max _{y}}$ ${\displaystyle \textstyle \min =(\min _{x},\min _{y})}$ ${\displaystyle \textstyle \max =(\max _{x},\max _{y})}$

Mathematically, the following applies to a MUR for all objects and dimensions : ${\displaystyle o}$ ${\displaystyle d}$

${\displaystyle \forall o\forall d\quad {\mbox{min}}_{d}\leq o_{d}\leq {\mbox{max}}_{d}}$

Being the largest and the smallest vector with this property are, so there is no smaller rectangle with this property. ${\displaystyle {\mbox{min}}}$ ${\displaystyle {\mbox{max}}}$

Extensiveness and monotony

As a shell operator, MUR have important properties for use in algorithms. Above all, the extensiveness and the monotony are important ${\displaystyle A\subseteq \operatorname {MUR} (A)}$

${\displaystyle A\subseteq B\Rightarrow \operatorname {MUR} (A)\subseteq \operatorname {MUR(B)} }$

In search trees like the R-tree, they are used to increase efficiency. It allows extensivity to exclude all subtrees in the search on the basis of MUR of the subtree: . The monotony also allows query areas to be assessed using their MUR. ${\displaystyle x\notin \operatorname {MUR} (A)\Rightarrow x\notin A}$

If objects are given, then applies ${\displaystyle n}$ ${\displaystyle A_{i},i=1\dots n}$

${\displaystyle \operatorname {MUR} \left(\bigcup _{i=1}^{n}A_{i}\right)=\operatorname {MUR} \left(\bigcup _{i=1}^{n}\operatorname {MUR} \left(A_{i}\right)\right)}$

The exact MUR of an object can therefore be calculated solely on the basis of the MURs of sub-objects.

Approximation using a minimally surrounding rectangle

Extended objects such as polygons can be approximated by their MUR. The advantage of using MURs compared to the convex hull of an object, for example, is the significantly lower memory requirement and the faster calculation of overlaps. These advantages are bought with a poor approximation accuracy . However, the advantages clearly outweigh this, especially on geographic data such as maps .