Minimum bounding rectangle

The minimum bounding rectangle (MBR), also known as the smallest enclosing rectangle, is the rectangle of minimum area that fully encloses a given set of points or a polygon in the Euclidean plane.^[1] In computational geometry, it is fundamentally defined for the convex hull of the input points, as the optimal rectangle bounds the hull rather than individual points.^[2] A defining property of the MBR is that its minimum-area configuration has at least one side collinear with an edge of the convex hull, a theorem established in early work on geometric optimization.^[2] Computing the MBR involves first obtaining the convex hull in O(n log n) time, followed by the rotating calipers algorithm, which identifies the optimal orientation in linear O(n) time relative to the hull's vertices.^[2] This method, introduced by Toussaint in 1983, exploits antipodal pairs of hull edges to efficiently evaluate candidate rectangles.^[2] The MBR finds broad applications in fields such as computer graphics for object collision detection, spatial databases for indexing via approximations like axis-aligned variants, and metrology for estimating form errors in manufactured parts.^[2] While exact algorithms suffice for small inputs, approximations are used for large-scale or higher-dimensional extensions to balance computational efficiency with near-optimal enclosure.^[1]

Definition and Fundamentals

Definition

The minimum bounding rectangle (MBR), also known as the smallest enclosing rectangle, of a set of points P = \{(x_i, y_i) \mid i = 1, \dots, n\} in the Euclidean plane is the rectangle of smallest area that contains all points in P. Equivalently, among all rectangles enclosing P, it is the one that minimizes the product of its width and height. In the special case of an axis-aligned minimum bounding rectangle (where the sides are parallel to the coordinate axes), the MBR can be computed directly from the extrema of the coordinates as follows:

\begin{align*} \min_x &= \min_i x_i, \\ \max_x &= \max_i x_i, \\ \min_y &= \min_i y_i, \\ \max_y &= \max_i y_i, \end{align*}

with area A = (\max_x - \min_x) \times (\max_y - \min_y). This formulation provides the tightest axis-aligned enclosure but may not yield the global minimum area if rotation is permitted. For more complex objects such as polygons or general shapes, the MBR is defined as the smallest rectangle enclosing the entire boundary and interior of the object; for simple polygons (convex or concave), this is equivalent to the MBR of the vertex set, as the enclosure must cover all extremal points. The concept of the minimum bounding rectangle originated in the computational geometry literature of the 1970s, building on earlier bounding box ideas from computer graphics in the 1960s and 1970s.^[3]

Geometric Properties

The minimum bounding rectangle (MBR) for a finite set of points in the plane is defined as the rectangle of minimal area that encloses all the points, with its boundary supported by points from the convex hull of the set. For convex polygons, an MBR of minimal area has at least one side collinear with an edge of the polygon, ensuring optimality by aligning the rectangle with the extremal features of the shape.^[4] This property holds because any smaller rectangle would fail to enclose the polygon if none of its sides coincide with a hull edge, as established through the geometry of supporting lines.^[5] The dimensions of the MBR correspond to the widths of the point set measured along two orthogonal directions, where the width in a given direction is the distance between parallel supporting lines perpendicular to that direction—known as the caliper diameter. The area of the MBR is the product of these orthogonal widths, and the minimal-area configuration selects the orientation that minimizes this product. This relates the MBR to the diameter of the set (the maximum caliper diameter over all directions) and the minimum width (the smallest caliper diameter), as the optimal MBR balances orthogonal caliper diameters to achieve the tightest enclosing fit without exceeding the set's extremal extents in any direction.^[4] Proofs of this minimization rely on the rotational invariance of caliper measurements and the convexity of the hull, showing that candidate orientations are limited to those aligned with hull edges.^[5] Degenerate cases arise when the point set lacks sufficient dimensionality. If all points are collinear, the convex hull is a line segment, and the MBR collapses to that segment with zero area and perimeter $2 \times segment length. For a single point, the MBR is a degenerate rectangle of zero area and zero perimeter at that point's location. These cases are handled by the convex hull computation, which reduces to the extremal points.^[5]

Axis-Aligned Minimum Bounding Rectangle

The axis-aligned minimum bounding rectangle (AAMBR), also referred to as an axis-aligned bounding box (AABB) in two dimensions, is the smallest rectangle whose sides are parallel to the coordinate axes and that fully encloses a given set of points or a geometric object.^[6] Its edges are horizontal and vertical, aligning directly with the x- and y-axes of the Cartesian coordinate system, without any rotation required for computation.^[6] The AAMBR is determined solely by the extrema of the coordinates in the input set. Specifically, for a set of n points P = \{(x_1, y_1), \dots, (x_n, y_n)\}, the rectangle spans from \min_i x_i to \max_i x_i along the x-axis and from \min_i y_i to \max_i y_i along the y-axis:

[\min_i x_i, \max_i x_i] \times [\min_i y_i, \max_i y_i]

This formulation ensures the rectangle is the tightest possible under the axis-alignment constraint.^[6] The computation involves a single linear pass over the points to identify these minimum and maximum values, achieving O(n) time complexity.^[6] The following pseudocode illustrates a straightforward implementation for computing the AAMBR:

function computeAAMBR(points):
    if points is empty:
        return null
    min_x = +∞
    min_y = +∞
    max_x = -∞
    max_y = -∞
    for each point p in points:
        min_x = min(min_x, p.x)
        min_y = min(min_y, p.y)
        max_x = max(max_x, p.x)
        max_y = max(max_y, p.y)
    width = max_x - min_x
    height = max_y - min_y
    return [Rectangle](/page/Rectangle)(min_x, min_y, width, height)
function computeAAMBR(points):
    if points is empty:
        return null
    min_x = +∞
    min_y = +∞
    max_x = -∞
    max_y = -∞
    for each point p in points:
        min_x = min(min_x, p.x)
        min_y = min(min_y, p.y)
        max_x = max(max_x, p.x)
        max_y = max(max_y, p.y)
    width = max_x - min_x
    height = max_y - min_y
    return [Rectangle](/page/Rectangle)(min_x, min_y, width, height)

This approach highlights the simplicity of the method, requiring only basic comparisons and no preprocessing like convex hull construction.^[6] A key advantage of the AAMBR is its computational efficiency and ease of implementation in systems using orthogonal coordinates, such as many graphics and spatial indexing applications, where rapid enclosure checks are prioritized over minimal area.^[6] However, it can be suboptimal for datasets exhibiting rotational symmetry or elongation not aligned with the axes; for instance, a set of points forming a diagonal line from (0,0) to (1,1) results in a square AAMBR of side length 1 and area 1, enclosing significant empty space relative to the points' linear extent.^[6] Unlike the oriented minimum bounding rectangle, which permits rotation to achieve a potentially smaller enclosing area, the AAMBR remains fixed to the axes and may thus overestimate the spatial extent.^[6]

Oriented Minimum Bounding Rectangle

The oriented minimum bounding rectangle (O-MBR) is defined as the rectangle of smallest area that encloses a given set of points in the plane, where the rectangle's sides may be rotated by an arbitrary angle θ relative to the coordinate axes.^[5] Unlike fixed-orientation variants, this allows the rectangle to adapt to the geometric distribution of the points, potentially achieving a tighter enclosure for non-axis-aligned configurations.^[4] A key geometric insight is that the optimal orientation of the O-MBR aligns with the edges of the convex hull of the point set, as interior points do not influence the bounding rectangle.^[5] The area of the O-MBR is minimized by finding the rotation angle θ that minimizes the product of the width and height projections of the point set onto the rotated axes, where width(θ) and height(θ) represent the extents in the perpendicular directions.^[5] For a convex polygon, the O-MBR is unique in the sense that at least one of its sides must be collinear with an edge of the convex hull.^[3] This property ensures that the minimal enclosure is "supported" by the hull's boundary, simplifying the search for the optimal rectangle among a finite set of candidate orientations defined by the hull edges.^[3] As an illustrative example, consider a set of points forming a square rotated by 45 degrees with side length r; the axis-aligned minimum bounding rectangle in this case has an area of 2r², whereas the oriented minimum bounding rectangle aligns with the square's sides and has an area of r², demonstrating the potential area reduction through rotation.^[5] The axis-aligned minimum bounding rectangle represents a special case of the O-MBR when θ = 0.^[5]

Algorithms for Computation

Convex Hull-Based Methods

Convex hull-based methods for computing the minimum bounding rectangle (MBR) of a point set begin with preprocessing to compute the convex hull of the points, which can be done in O(n log n) time using the Graham scan algorithm or in O(n h) time using the Jarvis march (gift wrapping algorithm), where n is the number of points and h is the number of vertices on the hull. These algorithms identify the smallest convex polygon enclosing all points, typically resulting in h ≪ n for many distributions. A fundamental property is that the MBR of the original point set coincides with the MBR of its convex hull vertices, as the rectangle must enclose the extreme points defining the hull's boundary.^[5] This reduces the computational complexity by focusing only on the h hull vertices. For the axis-aligned variant, the MBR is obtained by finding the minimum and maximum x- and y-coordinates among these h vertices, which takes O(h) time and yields a rectangle with width equal to the difference in x-extrema and height equal to the difference in y-extrema.^[5] For the oriented MBR, which allows rotation to minimize area, the approach exploits the theorem that the minimum-area rectangle enclosing a convex polygon has at least one side collinear with an edge of the polygon.^[3] Thus, candidate orientations are tested by considering each of the h hull edges as a potential side: for a given edge direction θ, the coordinate system is rotated by θ, and the axis-aligned MBR is computed in the new system by projecting hull vertices onto the rotated axes to find extrema (O(h) per edge), yielding a total time of O(h²). The rectangle with the smallest area among these candidates is selected. This method can be optimized further using the rotating calipers technique to achieve O(h) time.^[7] As an example, when the input is already a convex polygon with h vertices, the hull computation is unnecessary, and directly applying the edge-testing procedure computes the oriented MBR in O(h²) time.^[5]

Rotating Calipers Algorithm

The rotating calipers algorithm computes the oriented minimum bounding rectangle (MBR) for a convex polygon by maintaining four supporting lines—referred to as calipers—that define the rectangle's boundaries and rotating them in a coordinated fashion to minimize the enclosed area. These calipers consist of two pairs of parallel lines, initially aligned with the axes at the polygon's extreme vertices (leftmost, rightmost, topmost, and bottommost). The method exploits the property that the optimal MBR has at least one side collinear with an edge of the convex hull, ensuring all candidate orientations are evaluated efficiently.^[5] Following the computation of the convex hull with h vertices (where h \leq n), the algorithm proceeds in the following steps:

Initialize the calipers to form the axis-aligned MBR by placing them at the extreme hull vertices and computing the initial width and height as the differences in x- and y-coordinates.
Identify the next "rotation event" as the smallest angle required for any caliper to align with the subsequent edge of the hull, considering the antiparallel rotation of the pairs (one pair rotates clockwise, the other counterclockwise).
Rotate both pairs of calipers simultaneously by this angle, advancing the supporting vertices to the new edge alignments; this occurs at O(h) discrete events, as each step processes at least one vertex transition.
At each event, recompute the rectangle's dimensions: the width as the distance between one pair of parallel calipers and the height between the other; calculate the area as their product and track the minimum across all configurations.
Terminate after a 180-degree rotation, as further rotation repeats the process due to the rectangle's symmetry.^[7]

The overall time complexity is O(n \log n), dominated by the O(n \log n) convex hull computation (e.g., via Graham scan), with the rotation phase requiring O(h) time for the O(h) events and O(1) work per event to update distances and areas.^[5] The algorithm's correctness relies on the fact that all local and global minima of the area function occur precisely when at least one caliper aligns with a hull edge; between these alignments, the area either increases monotonically or the minimum is not missed, as proven by the convexity of the hull and the continuous nature of the rotation. This discrete-event approach captures the optimum without exhaustive search. The method builds on foundational results establishing edge-collinearity for the minimum-area rectangle.^[7] For illustration, consider the caliper rotation visually: starting with horizontal and vertical lines tangent to the hull at extremes, the lines "pivot" around contact points, maintaining parallelism within pairs while the pairs remain perpendicular; each pivot advances to the next hull edge, sweeping the boundary until returning to the initial orientation. A pseudocode outline is provided below, assuming counterclockwise-ordered hull vertices V[0 \dots h-1] and indices i_0, i_1, i_2, i_3 for initial bottom, right, top, and left supports:

min_area = infinity
current_angle = 0
// Initialize supports: i_bottom=0, i_right, i_top, i_left based on extremes
while current_angle < π:
    // Compute next rotation angle θ as min of angles to next edges from each support
    θ = min(angle_to_next(i_bottom), angle_to_next(i_right), angle_to_next(i_top), angle_to_next(i_left))
    // Rotate all supports by θ (advance indices accordingly)
    advance_supports(θ)
    // Compute distances
    width = distance_between_calipers(i_left, i_right)  // Parallel pair 1
    height = distance_between_calipers(i_bottom, i_top)  // Parallel pair 2
    area = width * height
    if area < min_area:
        min_area = area
        record_configuration()
    current_angle += θ
return min_area and corresponding orientation
min_area = infinity
current_angle = 0
// Initialize supports: i_bottom=0, i_right, i_top, i_left based on extremes
while current_angle < π:
    // Compute next rotation angle θ as min of angles to next edges from each support
    θ = min(angle_to_next(i_bottom), angle_to_next(i_right), angle_to_next(i_top), angle_to_next(i_left))
    // Rotate all supports by θ (advance indices accordingly)
    advance_supports(θ)
    // Compute distances
    width = distance_between_calipers(i_left, i_right)  // Parallel pair 1
    height = distance_between_calipers(i_bottom, i_top)  // Parallel pair 2
    area = width * height
    if area < min_area:
        min_area = area
        record_configuration()
    current_angle += θ
return min_area and corresponding orientation

Each advance_supports and distance computation is O(1), ensuring efficiency.^[5]

Applications and Uses

In Computational Geometry

In computational geometry, minimum bounding rectangles (MBRs) play a crucial role in spatial indexing structures, enabling efficient querying of multidimensional data. In R-trees, each node is associated with an MBR that encloses the spatial objects in its subtree, facilitating nearest-neighbor searches by pruning irrelevant branches through overlap tests between the query region and node MBRs. This hierarchical approximation reduces the search space significantly, allowing logarithmic-time access for typical queries in large datasets. Similarly, in k-d trees, MBRs of subtrees serve to bound point distributions, enabling rapid elimination of non-intersecting regions during range or nearest-neighbor operations, thus optimizing traversal in balanced binary search trees for spatial points. MBRs are also fundamental in collision detection algorithms, where they provide a fast approximation for initial intersection tests between geometric objects. By first checking if the MBRs of two objects overlap—via simple coordinate comparisons such as \max(x_{\min_1}, x_{\min_2}) \leq \min(x_{\max_1}, x_{\max_2}) and analogously for the y-coordinates, which can be performed in constant O(1) time—expensive exact geometry computations are avoided unless necessary. This broad-phase filtering is essential in dynamic simulations, where it culls potential collisions from thousands of pairwise checks down to a manageable subset, improving overall efficiency in real-time applications. For point location and spatial partitioning, MBRs integrate seamlessly with quadtree structures to support efficient 2D range searches. In point region (PR) quadtrees, each node's square region acts as an MBR for its enclosed points, allowing query rectangles to traverse only relevant subtrees by testing intersections with these bounds, thereby reporting all points within a specified area in logarithmic expected time relative to the data size. This partitioning approach decomposes the plane into adaptive cells, minimizing the number of nodes visited during searches for scattered point sets. A practical application arises in mesh generation, where MBRs initialize the computational domain for Delaunay triangulation by defining a rectangular enclosure around input vertices or curve segments, ensuring the initial triangulation covers the entire region before refinement steps improve element quality. In dynamic scenes, oriented MBRs can provide tighter bounds than axis-aligned variants, reducing false positives in indexing and detection tasks.

In Geographic Information Systems

In geographic information systems (GIS), the minimum bounding rectangle (MBR), often referred to as a bounding box or envelope, serves as a fundamental spatial primitive for representing the extent of geographic features, such as points, lines, or polygons, by enclosing them within the smallest possible axis-aligned or oriented rectangle. This approximation simplifies complex geometries for efficient storage, querying, and analysis of large datasets, where exact shape computations would be computationally expensive.^[8]^[9] A primary application of MBRs in GIS is spatial indexing, where structures like R-trees and quadtrees use MBRs to partition and organize spatial data, enabling rapid retrieval for queries such as intersection or containment. For instance, in R-tree indexing, each node stores an MBR that bounds its child entries, allowing the system to prune irrelevant branches during searches and reduce query times from linear to logarithmic complexity for multidimensional data. This approach is widely adopted in systems like PostGIS and Oracle Spatial for handling vector data in urban planning or environmental monitoring.^[10]^[11] MBRs also facilitate map visualization and extent definition, where tools in software like ArcGIS generate MBRs to automatically set the display bounds for selected features, ensuring complete coverage without manual adjustment. In production mapping, oriented MBRs (rotated to minimize area) are used to create precise extents for charts or layouts representing clustered features, such as wildlife habitats or infrastructure networks, improving cartographic accuracy and reducing visual clutter.^[8]^[12] Beyond indexing and visualization, MBRs support topological and directional relation queries in GIS databases by approximating object interactions; for example, determining if one feature overlaps another via MBR intersection tests before refining with exact geometry. However, empirical studies highlight limitations, such as overestimation of extents for irregular shapes like coastlines, which can lead to false positives in queries and reduced efficiency in high-density datasets. Despite these, MBRs remain essential for scalable spatial analysis in applications ranging from disaster response routing to land-use classification.^[13]^[14]