Rectangle packing

Last updated

Rectangle packing is a packing problem where the objective is to determine whether a given set of small rectangles can be placed inside a given large polygon, such that no two small rectangles overlap. Several variants of this problem have been studied.

Contents

Packing identical rectangles in a rectangle

In this variant, there are multiple instances of a single rectangle of size (l,w), and a bigger rectangle of size (L,W). The goal is to pack as many small rectangles as possible into the big rectangle without overlap between any rectangles (small or large). Common constraints of the problem include limiting small rectangle rotation to 90° multiples and requiring that each small rectangle is orthogonal to the large rectangle.

This problem has some applications such as loading of boxes on pallets and, specifically, woodpulp stowage. As an example result: it is possible to pack 147 small rectangles of size (137,95) in a big rectangle of size (1600,1230). [1]

Packing identical squares in a rectilinear polygon

Given a rectilinear polygon (whose sides meet at right angles) R in the plane, a set S of points in R, and a set of identical squares, the goal is to find the largest number of non-overlapping squares that can be packed in points of S.

Suppose that, for each point p in S, we put a square centered at p. Let GS be the intersection graph of these squares. A square-packing is equivalent to an independent set in GS. Finding a largest square-packing is NP-hard; one may prove this by reducing from 3SAT. [2]

Packing different rectangles in a given rectangle

In this variant, the small rectangles can have varying lengths and widths, and they should be packed in a given large rectangle. The decision problem of whether such a packing exists is NP-hard. This can be proved by a reduction from 3-partition. Given an instance of 3-partition with 3m positive integers: a1, ..., a3m, with a total sum of m T, we construct 3m small rectangles, all with a width of 1, such that the length of rectangle i is ai + m. The big rectangle has width m and length T + 3m. Every solution to the 3-partition instance induces a packing of the rectangles into m subsets such that the total length in each subset is exactly T, so they exactly fit into the big rectangle. Conversely, in any packing of the big rectangle, there must be no "holes", so the rectangles must not be rotated. Therefore, the packing must involve exactly m rows where each row contains rectangles with a total length of exactly T. This corresponds to a solution of the 3-partition instance. [3] [4]

When there is an additional restriction that the packing must be exact (with no wasted space), the small rectangles may be rotated only by multiples of 90°. In this case, the problem is in NP. Without this requirement, the small rectangles may be rotated in arbitrary angles. In this more general case, it is not clear if the problem is in NP, since it is much harder to verify a solution. [4]

Packing different rectangles in a minimum-area rectangle

In this variant, the small rectangles can have varying lengths and widths, and their orientation is fixed (they cannot be rotated). The goal is to pack them in an enclosing rectangle of minimum area, with no boundaries on the enclosing rectangle's width or height. This problem has an important application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server. The problem is NP-complete in general, but there are fast algorithms for solving small instances. [5] [6]

Related Research Articles

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:

<span class="mw-page-title-main">Polyomino</span> Geometric shapes formed from squares

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.

<span class="mw-page-title-main">Packing problems</span> Problems which attempt to find the most efficient way to pack objects into containers

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, and technology mapping in FPGA semiconductor chip design.

Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint.

<span class="mw-page-title-main">Guillotine cutting</span> Process of producing small rectangular items of fixed dimensions

Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine.

<span class="mw-page-title-main">Tatamibari</span> Logic puzzle

Tatamibari is a type of logic puzzle designed and published by Nikoli. The puzzle is based on Japanese tatami mats.

In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem".

The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely:

In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin packing problem is a list of objects of specific sizes and a size for the bins that must contain the objects—these object sizes and bin size are numerical parameters.

In computational complexity, an NP-complete problem is weakly NP-complete if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved, rather than the base-two logarithms of their magnitudes. Such algorithms are technically exponential functions of their input size and are therefore not considered polynomial.

<span class="mw-page-title-main">Rectilinear polygon</span> Polygon in which all angles are right

A rectilinear polygon is a polygon all of whose sides meet at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons.

<span class="mw-page-title-main">3-dimensional matching</span>

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices.

A geometric separator is a line that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset is small.

In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.

In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

In geometry, a partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

The strip packing problem is a 2-dimensional geometric minimization problem. Given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip minimizing its height. This problem is a cutting and packing problem and is classified as an Open Dimension Problem according to Wäscher et al.

Parallel task scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule. In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter pj and a size parameter qj, and it must run for exactly pj time-steps on exactly qj machines in parallel.

References

  1. ↑ Birgin, E G; Lobato, R D; Morabito, R (2010). "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle". Journal of the Operational Research Society. 61 (2): 306–320. doi:10.1057/jors.2008.141. S2CID   12718141.
  2. ↑ Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L. (1981-06-13). "Optimal packing and covering in the plane are NP-complete". Information Processing Letters. 12 (3): 133–137. doi:10.1016/0020-0190(81)90111-3. ISSN   0020-0190.
  3. ↑ Demaine, Erik D.; Demaine, Martin L. (2007-06-01). "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity". Graphs and Combinatorics. 23 (1): 195–208. doi:10.1007/s00373-007-0713-4. ISSN   1435-5914. S2CID   17190810.
  4. 1 2 Demaine, Erik (2015). "MIT OpenCourseWare – Hardness made Easy 2 – 3-Partition I". Youtube.
  5. ↑ Huang, E.; Korf, R. E. (2013-01-23). "Optimal Rectangle Packing: An Absolute Placement Approach". Journal of Artificial Intelligence Research. 46: 47–87. arXiv: 1402.0557 . doi: 10.1613/jair.3735 . ISSN   1076-9757.
  6. ↑ "Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites". www.codeproject.com. 14 June 2011. Retrieved 2020-09-09.
  7. ↑ Chan, T. M. (2003). "Polynomial-time approximation schemes for packing and piercing fat objects". Journal of Algorithms. 46 (2): 178–189. CiteSeerX   10.1.1.21.5344 . doi:10.1016/s0196-6774(02)00294-8.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.