Fact-checked by Grok 2 weeks ago

Rectangle packing

Rectangle packing, also known as the two-dimensional rectangular bin packing problem, is a challenge that involves arranging a of smaller rectangles—each defined by specific width and height dimensions—into one or more larger rectangular containers, such as bins or sheets, without overlaps or rotations (unless specified), to minimize the total area wasted or the number of containers required. This problem is NP-hard, meaning that finding an optimal solution becomes computationally infeasible for large instances, and it generalizes the one-dimensional by incorporating spatial constraints in two dimensions. The significance of rectangle packing stems from its broad applicability in industrial and logistical contexts, where efficient resource utilization directly impacts costs and sustainability; for instance, it arises in cutting stock operations for materials like wood, paper, , and metal sheets in , as well as in pallet loading for transportation and in , aircraft , and automotive assembly lines. Real-world challenges, such as the ROADEF 2018 competition on glass cutting or ESICUP benchmarks for vehicle loading, highlight its relevance, with research evolving from early studies in the 1960s to over 400 publications by the 1990s and continued growth into the 2020s, driven by increasing computational power and advancements. Solution approaches to rectangle packing are categorized into exact methods, which guarantee optimality for small instances using techniques like (pioneered by Gilmore and Gomory in 1961), branch-and-bound, or dynamic programming, and approximate methods, including constructive heuristics (e.g., bottom-left fill or first-fit decreasing) for quick near-optimal placements and metaheuristics such as genetic algorithms, , or for tackling larger, more complex variants like those allowing rotations, cuts, or multiple bin sizes. Variants extend the core problem to include constraints like item orientation, demand quantities, or open dimensions (e.g., unbounded height in strip packing), with ongoing research focusing on hybrid algorithms and integrations to improve performance in dynamic, scenarios.

Fundamentals

Definition and Variants

Rectangle packing refers to the problem of arranging a of smaller rectangles within a larger , such as a rectangular or a , such that no two rectangles overlap and all edges are aligned orthogonally to the container's axes, unless rotations are permitted under specific constraints. The smaller rectangles may be identical in dimensions or heterogeneous, and the container can have fixed dimensions or variable ones to be minimized. This problem arises in applications like , where material waste must be minimized, and in for tasks such as memory allocation. Mathematically, the problem can be formulated as follows: given a set of n rectangles R_i with widths w_i > 0 and heights h_i > 0 for i = 1, \dots, n, and a rectangular of fixed width W and H, determine positions (x_i, y_i) for each selected rectangle R_i such that $0 \leq x_i \leq W - w_i, $0 \leq y_i \leq H - h_i, and the interiors of the placed rectangles do not intersect. The primary objectives include maximizing the number of rectangles packed, maximizing the total value or area covered, or minimizing unused space (waste) within the . Constraints on rotations vary: fixed prohibits any rotation; 90° rotations allow swapping width and height; and arbitrary rotations permit any angle, though the latter is less common in orthogonal variants due to increased complexity. Key variants distinguish the problem based on item uniformity, container type, and packing structure. For item types, identical rectangle packing involves uniform dimensions, while heterogeneous packing deals with varying sizes. Structural variants include orthogonal packing, the baseline where all placements are axis-aligned without further restrictions; packing, which requires the to be recursively partitioned by cuts from one side to the opposite, enabling efficient cutting in ; shelf packing, where rectangles are grouped into strips (shelves) of equal height before stacking; and packing, which minimizes the length (e.g., height) of a with one unbounded dimension, such as fixed-width infinite-height. These variants maintain non-overlap and orthogonal constraints but differ in feasibility and optimization focus. A simple illustrative example is packing four identical $1 \times 1 squares into a $2 \times 2 square , which achieves a perfect packing density of 1 (full utilization of the container area).

History

The roots of rectangle packing research trace back to the 1960s in , where it emerged as a key component of cutting stock problems aimed at minimizing waste in material utilization for industries like and production. Early formal studies in the 1970s focused on algorithmic approaches for orthogonal packings, with L. Combes introducing rules for packing rectangles into rectangular arrangements in 1976. By the late 1970s and early , seminal work by B. S. Baker, E. G. Coffman Jr., and R. L. Rivest formalized the problem of orthogonal packings in two dimensions, including partitions that restrict cuts to straight lines dividing the container into sub-rectangles. These efforts highlighted the practical challenges of exact solutions for non-trivial instances, laying the groundwork for subsequent theoretical analysis. In the , the field advanced with proofs establishing the of rectangle packing variants, often via reductions from the strongly NP-complete 3-partition problem, underscoring the computational intractability even for restricted cases like strip packing. This shift prompted a move toward approximation algorithms, with key milestones in the including shelf-based heuristics developed by E. G. Coffman Jr. and colleagues, which pack rectangles into horizontal "shelves" to achieve bounded performance guarantees relative to optimal packings. Influential researchers like B. S. Baker contributed to these developments by analyzing guillotine-constrained packings, while the recognition of drove the transition from exact methods to efficient approximations suitable for real-world applications. The and saw a surge in heuristics for heterogeneous rectangle packing, incorporating techniques such as genetic algorithms to handle diverse item sizes and orientations, as explored in works optimizing packing sequences and layouts. Erik D. Demaine and collaborators advanced the theoretical understanding of related problems, including packing identical squares into polygons, revealing for grid-based variants and inspiring algorithmic innovations. This era emphasized practical heuristics over exact solutions due to the problem's intractability, with genetic and evolutionary methods enabling better handling of complex, heterogeneous instances. Recent developments through 2025 have integrated metaheuristics like genetic algorithms into extensions such as packing, while techniques, including machine learning-enhanced heuristics, support real-time optimization in for dynamic packing scenarios. These advances, building on the foundational shift to approximations, continue to prioritize scalable solutions for industrial applications.

Packing Identical Items

Identical Rectangles in a Fixed Rectangle

The problem of packing identical rectangles into a fixed rectangular container involves arranging as many non-overlapping copies of a smaller rectangle of fixed dimensions l \times w as possible within a larger of dimensions L \times W, where the objective is to maximize the number n of packed rectangles or the packing density defined as \frac{n \cdot l \cdot w}{L \cdot W}. Rotations by 90 degrees are typically permitted, allowing rectangles to be placed with either orientation, while all placements must be orthogonal to the container's axes. This formulation arises in practical applications such as pallet loading and stowage optimization in industries like woodpulp production, where uniform items must be efficiently arranged to minimize waste. Constraints require orthogonal alignment of all rectangles, prohibiting overlaps or extensions beyond the container boundaries, with no additional restrictions on weight, fragility, or other item properties. Waste minimization is achieved through structured patterns, often leveraging to explore feasible arrangements systematically. For cases without rotation, the maximum number of rectangles is given by \lfloor L / l \rfloor \times \lfloor W / w \rfloor, representing a simple grid packing that serves as a for calculations. Optimal packings frequently employ patterns, where the container is recursively divided by straight cuts parallel to the axes, enabling perfect or near-perfect fits in many instances by combining basic blocks like L-shaped subdivisions and non- first-order cuts into five subrectangles. These patterns facilitate solutions for instances, such as the I and II test sets, by reducing the search space through raster points—discrete positions aligned with multiples of l and w. A representative example from woodpulp stowage involves packing 147 rectangles of size $137 \times 95 into a of $1600 \times 1230, achieving a of approximately 97.2% through a combination of rotated and non-rotated placements in a recursive structure. Another case packs 255 such rectangles into $2530 \times 1320, improving upon prior heuristics and demonstrating the efficacy of partitioning approaches in industrial contexts with near-optimal waste reduction.

Identical Squares in a Rectilinear Polygon

The problem of packing identical squares into a involves placing the maximum number of non-overlapping, axis-aligned squares of fixed side length s within a simple bounded by orthogonal edges, ensuring the squares remain entirely inside the polygon without crossing boundaries. Candidate positions for placing these squares are typically determined by the polygon's vertices or the intersections of extended horizontal and vertical lines from those vertices, which discretize the possible locations into a aligned with the polygon's grid-like structure. This setup contrasts with packing into a fixed by accounting for the irregular, potentially boundaries of the rectilinear polygon, which may create forbidden regions or constraints on feasible placements. To model this problem, an is constructed where each vertex represents a candidate position for a square of side s, and an edge connects two vertices if the corresponding squares would overlap when placed at those positions. The maximum independent set in this graph then corresponds to the largest collection of non-overlapping squares that can be packed into the , as selecting non-adjacent vertices ensures no overlaps. The graph can be built efficiently by checking pairwise overlaps among candidates, leveraging the orthogonal nature of the polygon to limit computations to grid-aligned checks. This packing problem is NP-hard, even for simple orthogonal polygons without holes, as demonstrated by a reduction from a variant of 3-SAT (specifically, Monotone-Clover-3SAT) that encodes logical variables and clauses into polygon gadgets constraining square placements (as proven in 2024). For illustration, consider a small rectilinear polygon resembling a staircase with indentations: candidate positions near the steps may form a conflict graph with cycles or cliques, where selecting a square in one indentation blocks adjacent ones, mirroring the independent set challenges in the reduction's clause gadgets and highlighting why exhaustive enumeration becomes infeasible for larger instances. Practical applications include irregular floor plans with uniform square tiles to maximize coverage while respecting architectural boundaries, and in VLSI chip design, where square modules must be packed into regions defined by wiring channels or pre-placed components to optimize utilization.

Packing Heterogeneous Items

Different Rectangles in a Fixed Rectangle

The problem of packing different into a fixed , also known as the two-dimensional geometric knapsack or shelf packing decision variant, is defined as follows: given a set of n with fixed widths w_i and heights h_i for i = 1, \dots, n, and a fixed rectangular bin of dimensions W \times H, determine whether all rectangles can be placed orthogonally without overlap inside the bin, optionally allowing 90° rotations for each rectangle. The placements must be axis-aligned, with no rectangles extending beyond the bin boundaries or overlapping interiors. This decision problem is NP-complete, even without rotations, as shown by a reduction from the one-dimensional bin packing problem. The problem is strongly NP-hard, inheriting complexity from the one-dimensional case. In the exact packing subcase, where the total area of the rectangles equals W \times H (zero waste), the problem remains NP-hard but belongs to NP, since a polynomial-time verifiable certificate consists of the exact coordinates (x, y positions) and orientations for each rectangle's bottom-left corner. Key challenges arise from the heterogeneity of rectangle sizes, leading to spatial fragmentation—irregular gaps or slivers between placed items—and unintended voids that hinder complete filling of the bin, even when the aggregate area condition holds. These issues are exacerbated without rotations, as fixed orientations may leave narrow unfilled regions that cannot accommodate remaining items, whereas 90° rotations allow reorientation to better match void dimensions and improve fit. Enabling rotations can significantly reduce wasted space in practice. A central metric is packing density, computed as \frac{\sum_{i=1}^n w_i h_i}{W H}, which quantifies utilization efficiency and underscores the impact of voids (densities often below 80% in suboptimal packings). The problem admits offline and online variants: offline assumes all rectangles are available upfront for coordinated placement, enabling higher densities, while online requires irrevocable placement of each arriving rectangle without knowledge of future items, typically yielding lower densities due to premature commitments. The offline fixed-bin feasibility contrasts with extensions minimizing the bin area, which optimize W and H rather than testing a preset container.

Different Rectangles in a Minimum-Area Rectangle

The problem of packing different into a minimum-area enclosing involves arranging a given set of heterogeneous , each with fixed dimensions (w_i, h_i), into an enclosing of width W and height H such that no overlaps occur and the product W \times H is minimized. Rotations by 90 degrees may be permitted for some or all , adding flexibility but increasing computational difficulty, while fixed orientations enforce stricter alignment. The enclosing has no predefined bounds, distinguishing this from fixed-container variants where feasibility within a given bin is assessed. Key variants include guillotine-constrained packings, where the arrangement must be achievable through a sequence of recursive straight cuts parallel to the axes, from one edge to the opposite, facilitating practical processes like sheet cutting. Another variant considers subset packing, where the goal is to select the maximum disjoint set of rectangles that can be packed into an enclosing of minimum area, akin to a knapsack extension prioritizing packed item value or count. The decision version—determining if all rectangles can fit into a fixed enclosing —is NP-complete, as shown by reduction from the ; the minimum-area optimization inherits this complexity, with binary search enabling checks for area bounds. This complexity underscores the challenge for heterogeneous instances, though exact branch-and-bound methods solve small cases optimally, such as up to 10 rectangles. Heuristics, like absolute placement approaches that fix x-coordinates before y-coordinates, often yield solutions within 5% of optimality for such small instances (n \leq 10). A practical example is image atlas creation in , where diverse textures are packed to minimize the atlas size for efficient rendering and memory use in web graphics applications. Lower bounds provide essential context for assessing solution quality: W \geq \max_i w_i, H \geq \max_i h_i, and W \times H \geq \sum_i w_i h_i, with tighter estimates incorporating pairwise sums for potential shelf or row packings, such as W \geq \max w_i + \sum_{j \neq i} \min(w_j, h_j) under assumptions to account for secondary placements. These bounds, derived from subset sum relaxations and total area considerations, guide in exact solvers and evaluate performance. Recent research as of 2025 has incorporated techniques, such as , to improve performance for larger heterogeneous instances in dynamic settings.

Algorithms and Techniques

Exact Methods

Exact methods for rectangle packing aim to find provably optimal solutions by systematically exploring the solution space, often at the cost of high computational demands. These approaches are particularly effective for small to medium-sized instances where optimality is paramount, such as in precision manufacturing or custom design applications. Common techniques include branch-and-bound, dynamic programming restricted to cuts, and integer formulations that model positions and non-overlap constraints explicitly. Branch-and-bound algorithms perform an exhaustive search over possible placements while pruning branches that cannot lead to better solutions using lower bounds on the objective, such as minimizing the area or . In these methods, partial packings are evaluated by computing a lower bound, for example, the current filled area plus the remaining item area divided by the maximum possible , which must not exceed the target size to justify further exploration. A seminal uses a strategy to prioritize promising partial packings, achieving optimal solutions for instances with up to 20-30 rectangles by efficiently enumerating orthogonal placements without rotations. Dynamic programming is well-suited for guillotine packings, where cuts divide the container into sub-rectangles recursively, allowing a state-based recurrence. The state is typically defined by the current sub-rectangle dimensions (width w, height h) and the remaining set of items S, with the value function f(w, h, S) representing the maximum value (e.g., area covered or ) achievable in that subproblem. The recurrence considers all possible cuts: either a horizontal cut at height h' yielding f(w, h', S_1) + f(w, h - h', S_2), or a vertical cut at width w' similarly, where S_1 and S_2 S, optimized over feasible partitions. This approach traces back to the foundational work on multistage cutting stock problems, enabling exact solutions for guillotine-constrained instances with dozens of items. Integer linear programming (ILP) models the problem using continuous variables for item positions x_i, y_i (bottom-left coordinates of item i) and variables to enforce non-overlap between pairs. For each pair i < j, four disjunctive constraints ensure separation: x_i + w_i \leq x_j, x_j + w_j \leq x_i, y_i + h_i \leq y_j, or y_j + h_j \leq y_i, with binaries selecting exactly one active constraint per direction. The objective minimizes waste, such as the container height H subject to y_i + h_i \leq H for all i, plus bounds on widths and non-negativity. Solvers like branch-and-cut can handle instances with up to 15-20 heterogeneous rectangles, though the quadratic number of pairwise constraints and the inherent NP-hardness limit scalability. These exact methods exhibit exponential time complexity, rendering them impractical for instances exceeding 20 items due to the combinatorial explosion in placement possibilities. However, for packing identical rectangles, optimality can often be achieved more efficiently through enumeration of possible tilings, where feasible patterns are generated and selected to cover the container without waste, as demonstrated in pallet loading problems solvable for hundreds of identical items. For larger instances, heuristic methods provide near-optimal solutions rapidly.

Approximation and Heuristic Approaches

Approximation and heuristic approaches for rectangle packing prioritize computational efficiency over guaranteed optimality, making them suitable for large-scale instances where exact methods become infeasible due to exponential time complexity. These techniques often rely on greedy placement rules, sorting strategies, and optimization frameworks to produce packings with high density—defined as the ratio of packed item area to container area—while minimizing wasted space. Seminal developments in the 1980s established foundational guarantees, such as asymptotic performance ratios relative to the optimal solution, enabling practical deployment in industrial settings. Shelf packing algorithms form a core class of heuristics, organizing rectangles into successive horizontal "shelves" where each shelf accommodates items of similar height to maximize utilization within a fixed-width container, such as in strip packing. Rectangles are typically sorted in decreasing order of height before placement. The Next-Fit Decreasing Height (NFDH) heuristic, a prominent example, packs the next rectangle into the current shelf if it fits horizontally; otherwise, it closes the shelf and opens a new one at the height of the current rectangle. This simple O(n log n) procedure, due to sorting, yields a packing height of at most 2 \cdot OPT + 1 for strip packing, where OPT is the optimal height, implying a worst-case density of at least 1/2 + \epsilon for small \epsilon depending on instance size. NFDH performs well empirically on uniform distributions but can suffer from fragmentation in heterogeneous cases. Level algorithms extend shelf packing by treating levels as horizontal bands that span the container width, allowing more flexible placement across multiple levels. The First-Fit Decreasing Height (FFDH) variant sorts rectangles by decreasing height and attempts to place each into the lowest existing level where it fits horizontally; if none exists, a new level is created. FFDH achieves an improved asymptotic approximation ratio of approximately 1.7 \cdot OPT for strip packing height, enhancing density guarantees to roughly 0.59 of optimal in the limit. For heterogeneous items, bottom-left fill places each rectangle (sorted by area or height) in the lowest possible y-coordinate and then the leftmost x-coordinate without overlap, promoting compact layouts. This heuristic, analyzed for bounded waste, often yields densities exceeding 85% in practice. Skyline variants maintain an outline of the current packing "skyline" to identify candidate positions efficiently, reducing placement time to O(n log n) while handling irregular shapes better than pure bottom-left. Guillotine heuristics generate packings through recursive orthogonal cuts that divide the container into sub-rectangles, mimicking manufacturable patterns like those in sheet metal cutting. Starting with the full container, an item is placed and a guillotine cut (horizontal or vertical) separates the remaining space, recursing on sub-regions until all items are packed. These methods, often combined with best-fit selection, ensure constraint-compliant layouts and achieve densities comparable to level algorithms, with empirical improvements via priority-based item ordering. Metaheuristics address the limitations of greedy methods by exploring solution spaces globally. Genetic algorithms represent packings as chromosome strings encoding item orders and orientations, evolving populations through crossover and mutation, decoded via heuristics like bottom-left for fitness evaluation based on density or height. Such approaches, seeded with NFDH solutions, have demonstrated superior performance on non-guillotine instances. Simulated annealing iteratively perturbs placements—shifting, swapping, or rotating rectangles—and accepts suboptimal moves with probability e^{-\Delta E / T}, where \Delta E is the density penalty and T decreases over time, effectively handling rotations and achieving near-optimal densities. Recent advancements include reinforcement learning approaches, such as Q-learning for optimizing item sequences and orientations, achieving improved performance on large instances. For online variants, algorithms like First-Fit Decreasing sort incoming rectangles by decreasing size and place each in the first feasible position, adapting shelf or level rules for dynamic arrivals. Empirical evaluations on benchmark instances with n=100 heterogeneous rectangles show these heuristics attaining average densities of 80-95%, with skyline and genetic methods often reaching the upper end for strip packing height minimization via bottom-left decoding. For instance, NFDH and FFDH typically achieve 82-90% density on uniform random inputs, while metaheuristics push beyond 92% after refinement, validating their scalability to thousands of items.

Computational Complexity

Hardness Results

The decision problem of determining whether a set of heterogeneous rectangles can be packed without overlap into a fixed-size rectangular bin, assuming no rotations, is NP-complete. This result follows from a polynomial-time reduction from the bin packing problem, which is itself NP-complete; specifically, each item size in a bin packing instance is transformed into a unit-height rectangle of that width, while the target bin becomes an enclosing rectangle with height equal to the number of bins in the instance and width equal to the bin capacity, ensuring that feasible packings correspond exactly to valid bin assignments. To establish strong NP-completeness, reductions from the 3-partition problem are employed, where the input consists of 3n positive integers bounded between B/4 and B/2 that sum to nB; these are mapped to rectangles whose widths correspond to the integers, with heights set to ensure that valid packings require triples of widths summing precisely to one-third of the bin width in each of three horizontal strips, mirroring the partitioning constraint. Packing identical squares into a rectilinear polygon is also NP-hard. This hardness is proven via a reduction from planar 3-SAT, constructing an orthogonal polygon with gadgets for variables (allowing two possible square placements corresponding to true/false assignments), clauses (enforcing at least one literal satisfaction through restricted packing positions), and propagation mechanisms (such as PUSH and OR gadgets) to ensure that a perfect packing of unit squares exists if and only if the 3-SAT formula is satisfiable; the construction yields a simple, orthogonally convex polygon of polynomial size. The optimization problem of packing heterogeneous rectangles into a minimum-area enclosing rectangle is NP-hard, as solving it would allow deciding arbitrary instances of the fixed-bin decision problem by binary search on the area. In contrast, the complexity of exact rectangle packing allowing 90-degree rotations remains an open problem, though it is widely suspected to be NP-hard based on the intractability of related variants. Special cases admit polynomial-time solvability. For identical rectangles packed into a fixed bin without rotations, feasibility can be checked in linear time by dividing the bin dimensions by the rectangle dimensions to compute the maximum fitting count along width and height, verifying if the total required equals or exceeds this capacity. Similarly, guillotine packing variants—where the packing can be obtained by recursively dividing the bin with straight cuts parallel to the sides—are solvable in polynomial time for cases such as identical small rectangles or targeted densities, using dynamic programming to enumerate cut sequences and subtree assignments.

Approximation Ratios and Bounds

In strip packing, where rectangles of varying sizes are packed into a strip of fixed width to minimize height, the Next-Fit Decreasing Height (NFDH) algorithm sorts rectangles by nonincreasing height and places each on the lowest existing level that accommodates it, creating a new level otherwise. This yields an approximation ratio of $2 \mathrm{OPT} + 1, where OPT denotes the optimal height, with the asymptotic bound of 2 being tight. For heterogeneous rectangle bin packing, where the goal is to pack into the minimum number of unit-square bins, the first-fit decreasing height (FFDH) heuristic—sorting by nonincreasing height and assigning each to the first bin with sufficient space on an existing shelf or starting a new shelf—achieves an approximation ratio of $2 \mathrm{OPT}. Asymptotic polynomial-time approximation schemes (APTAS) exist for packing identical , enabling packings with density approaching $1 - \epsilon for any \epsilon > 0 in polynomial time relative to \frac{1}{\epsilon}. For instance, when packing identical squares into a fixed to maximize the number packed, an asymptotic PTAS guarantees a within (1 + \epsilon) of the optimum asymptotically as the number of squares grows. Resource augmentation techniques enhance solvability by relaxing the bin constraints slightly. For any \epsilon > 0, there exist polynomial-time algorithms that pack a subset of rectangles into augmented by a factor of $1 + \epsilon in one (e.g., ), achieving total at least (1 - \epsilon) times the optimum for the unaugmented unit-square . This approach admits an asymptotic PTAS for strip packing even with 90° rotations allowed. Recent advances in the have improved ratios for restricted packings like and shelf variants using relaxations and configuration-based methods. For strip packing, where cuts must alternate between horizontal and vertical stages, a polynomial-time ( \frac{3}{2} + \epsilon )- exists, matching the known APX-hardness of \frac{3}{2} - \epsilon. For shelf variants, where packings are limited to horizontal shelves followed by vertical stacking, LP-based rounding yields ratios approaching \frac{4}{3} in .

Applications

Industrial and Manufacturing Uses

Rectangle packing plays a central role in the cutting stock problem within manufacturing, particularly for minimizing waste when cutting smaller rectangular items from larger stock sheets of materials like sheet metal, fabric, or plywood. The objective is to arrange the items orthogonally without overlap to maximize material utilization, often reducing scrap that would otherwise contribute to production costs and environmental impact. Seminal contributions, such as the column generation approach developed by Gilmore and Gomory, originated in the context of paper production but have been widely adapted for two-dimensional stock cutting in metalworking and textiles, enabling near-optimal patterns that balance demand fulfillment with minimal trim loss. In fabrication, cuts impose a structured on packing layouts, where each cut divides a into two smaller ones via a single straight line, ensuring compatibility with industrial and that perform efficient, high-volume orthogonal slicing. This method is prevalent in automotive and , where precise nesting of parts like brackets or panels from sheets avoids complex non-guillotine patterns that could complicate machinery setup. For fabric cutting in apparel or production, similar guillotine-based heuristics facilitate and while adhering to grain direction . Container loading in employs two-dimensional rectangle packing to optimize the floor projections of within trailers or shipping pallets, treating items as rectangles to maximize load and . For palletizing , such as boxed components in electronics assembly, identical rectangle arrangements ensure even weight distribution and compliance with transportation regulations. In the wood and industries, historical applications trace back to mid-20th-century wood panel cutting for furniture and wood-derived sheets, where packing algorithms addressed irregular demands from pulp processing; three-dimensional extensions build on these by stacking orthogonal two-dimensional layers to approximate bin packing for or rolled . Heuristic methods for these applications typically achieve significant waste reductions compared to manual layouts, with case studies in automotive nesting demonstrating substantial scrap minimization through genetic algorithm-based packing that nests irregular parts efficiently on standard coils. These gains underscore rectangle packing's on sustainable by curbing resource depletion in resource-intensive sectors. Recent as of 2025 explores variants like packing soft rotated rectangles for optimized containers in manufacturing irregular shapes.

Digital and Computational Uses

In very-large-scale integration (VLSI) design, rectangle packing arranges rectangular modules, such as logic blocks and memory units, on a chip to minimize overall area while avoiding overlaps and supporting efficient . The sequence-pair , a seminal method introduced by Murata et al., encodes possible placements as two permutations of module names, enabling optimization via to achieve near-optimal packings in O(n²) time for n modules. This approach has been foundational, with extensions handling symmetry and wirelength minimization, and guillotine partitions derived from packings facilitate hierarchical by allowing recursive subdivision of the layout. Rectangle packing plays a key role in for generating atlases, where disparate rectangular images—such as sprites, UI elements, or environment maps—are consolidated into a single to reduce GPU state changes, lower , and boost rendering in games and web applications. Algorithms like best-fit decreasing height order pack these rectangles into a minimal-area atlas, often achieving high densities for power-of-two sized inputs, with heuristics prioritizing larger items first to minimize fragmentation. For instance, in real-time applications, skyline-based methods scan horizontal profiles to insert rectangles efficiently, ensuring seamless without seams. In , rectangle packing optimizes the 2D arrangement of sliced models or multi-part assemblies on the build plate, maximizing utilization to reduce support material and print times, particularly for heterogeneous prints involving varied geometries. Pixel-based or contour-approximated packing algorithms handle irregular shapes by treating them as bounding rectangles, allowing rotations and nesting to fill gaps, with reported improvements in plate coverage up to around 90% in . In cloud-based manufacturing, such methods group compatible tasks into shared prints, significantly cutting auxiliary setup times compared to sequential processing. Emerging applications in the 2020s leverage for rectangle packing in , modeling multi-dimensional bin packing—where servers act as containers and virtual machines or workloads as rectangles—to dynamically assign CPU, , and storage while minimizing energy costs and migrations. techniques, including , surpass classical heuristics by predicting workload patterns and achieving better packing densities in empirical tests on benchmarks like the Cutting Stock Dataset. Tools in exemplify this in digital workflows, employing imposition scripts based on bin-packing principles to arrange rectangular page elements on sheets for print-ready PDFs, optimizing media use in publishing.

Related Problems

Bin Packing Variants

Rectangle packing connects closely to the classic one-dimensional , where items of varying lengths are assigned to fixed-capacity bins to minimize the number of bins used, often serving as a foundational model for cutting stock optimization. In two dimensions, this extends to packing rectangular items orthogonally without overlap into fixed-size rectangular or square bins, again aiming to minimize the number of bins while respecting spatial constraints. This 2D variant inherits the of its 1D counterpart and introduces additional geometric challenges, such as arranging rectangles to avoid wasted space due to irregular shapes. A key distinction in rectangle bin packing lies between offline and online settings. In the offline case, the entire set of rectangles is known beforehand, enabling algorithms like First-Fit Decreasing Height (NFDH) to achieve asymptotic performance ratios close to 2 for strip packing variants, which bound the used height by twice the total area plus the tallest item. Conversely, the version processes rectangles sequentially without rearranging prior placements, leading to competitive ratios around 1.588 for advanced harmonic algorithms, though at the cost of higher space usage compared to offline solutions. These modes reflect practical scenarios, such as batch (offline) versus inventory loading (). Vector bin packing represents a multidimensional extension without geometric constraints, treating items as vectors of weights (e.g., demands like CPU and ) that must sum to at most the bin's capacity in each . For two dimensions, this variant admits algorithms with asymptotic ratios of approximately 1.405 plus a small , improving on earlier O(log d) bounds for higher dimensions, and is APX-hard even in . Unlike pure capacity-focused packing, geometric variants enforce non-overlapping orthogonal placements, which can increase the minimum bins needed; for instance, packing equal squares may require partitioning into size classes to approach optimal , adapting 1D fit techniques that classify items by size intervals for bounded . Hybrids like geometric multiple knapsack problems combine bin packing with value maximization: given a fixed number of bins, select and geometrically pack a subset of weighted rectangles to maximize total value without overlap. Recent frameworks provide efficient resource-augmented approximation schemes (ERAS) for such problems with convex fat objects in fixed dimensions, achieving (1+ε)-approximations in polynomial time while allowing bounded resource augmentation, thus bridging capacity and spatial constraints in applications like cloud resource allocation.

Geometric Packing Extensions

Geometric packing extensions generalize the rectangle packing problem to non-rectangular shapes and higher dimensions, introducing additional complexities in arrangement and optimization. These variants often yield lower packing densities compared to orthogonal rectangle packings due to the curved or irregular boundaries that prevent perfect . For instance, while rectangles can achieve densities approaching 1 in ideal cases, alternative shapes require or methods to maximize space utilization. Circle packing involves arranging non-overlapping circles within a rectangular or other bounded , a problem that extends by replacing straight-edged items with rotationally symmetric disks. Unlike rectangles, circles do not benefit from orthogonal constraints since rotations do not alter their shape, but the packing must ensure no intersections while maximizing the number or total area of circles. Seminal results establish that the densest infinite plane packing of equal circles achieves a of \pi / \sqrt{12} \approx 0.9069 via hexagonal arrangements, which serves as an upper bound for finite rectangular containers. In rectangular bounds, computational methods like quasi-Monte Carlo simulations or deterministic algorithms generate near-optimal packings, though densities typically fall below the hexagonal limit due to boundary effects. For example, packing 10 equal circles into a square yields a density of approximately 0.69. These approaches highlight the trade-off between computational efficiency and achieving densities lower than those possible with rectangles. Polygon packing further extends the problem to multi-sided shapes, distinguishing between orthogonal placements (axis-aligned edges) and those allowing arbitrary rotations. Orthogonal polygon packing mirrors rectangle constraints but accommodates non-rectangular profiles, often resulting in densities limited by edge alignments and wasted interstitial spaces. Allowing arbitrary rotations increases flexibility, enabling tighter nestings that improve densities, particularly for s like triangles or hexagons, where aids in filling gaps. Research on packings in rectangles shows that rotational variants can achieve higher densities than orthogonal ones. A review of irregular polygon packing underscores that density optimizations rely on geometric like Minkowski sums to detect overlaps. In three dimensions, box packing generalizes to arranging rectangular prisms (boxes) within larger containers, such as cubic bins or irregular volumes, while considering not only but also constraints. The three-dimensional is strongly NP-hard, even without stability, as it extends the 2D case by adding a height dimension that exponentially increases combinatorial possibilities. Incorporating vertical —ensuring stacked boxes do not topple under or load—further complicates solutions, requiring constraints on center-of-mass and surfaces. algorithms, such as layer-based or genetic methods, approximate optimal arrangements, with asymptotic performance ratios around 1.05-1.22 times the lower volume bound for large instances. Irregular shape nesting addresses packing non-rectangular, potentially or polygons into a , a critical extension for real-world items like patterns or metal sheets. This variant uses no-fit polygons (NFPs)—regions tracing one shape around another to define forbidden placements without overlap—to efficiently model geometric constraints. NFPs enable fast in optimization frameworks, supporting both exact and solvers for nesting problems. Complementing NFPs, phi-functions provide continuous mathematical descriptions of feasible positions, such as or conditions between shapes, formulated as \phi(A, B, r) \geq 0 where A and B are objects and r is relative position, allowing models for dense packings. These tools handle arbitrary rotations and translations, achieving high densities for industrial irregular sets, though computational costs rise with shape complexity. Guillotine packing variants in 3D impose recursive stage cuts—dividing the into sub-containers via planar guillotine slices—extending 2D guillotine methods to facilitate manufacturable cuttings in shipping and . This constraint ensures packings are decomposable by straight cuts, simplifying production but potentially lowering densities by restricting non-guillotine arrangements. Algorithms for 3D guillotine unbounded knapsack and cutting stock problems use dynamic programming to optimize under these rules, yielding approximation ratios of 1.691 + ε for strip packing variants. In shipping applications, such as container loading, 3D guillotine packings support efficient arrangement for transport, balancing volume utilization with load stability and accessibility for unloading.