|
Rectangle Packing
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. 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). Packing identi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Packing Problem
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. In a bin packing problem, you are given: * A ''container'', usually a two- or three-dimensional convex region, possibly of infinite size. Multiple containers may be given depending on the problem. * A set of ''objects'', some or all of which must be packed into one or more containers. The set may contain different objects with their sizes specified, or a single object of a fixed dimension that can be used repeatedly. Usually the packi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP (complexity)
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.''Polynomial time'' refers to how quickly the number of operations needed by an algorithm, relative to the size of the problem, grows. It is therefore a measure of efficiency of an algorithm. An equivalent definition of NP is the set of decision problems ''solvable'' in polynomial time by a nondeterministic Turing machine. This definition is the basis for the abbreviation NP; " nondeterministic, polynomial time". These two definitions are equivalent because the algorithm based on the Turing machine consists of two phases, the first of which consists of a guess abou ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Packing Problems
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. In a bin packing problem, you are given: * A ''container'', usually a two- or three-dimensional convex region, possibly of infinite size. Multiple containers may be given depending on the problem. * A set of ''objects'', some or all of which must be packed into one or more containers. The set may contain different objects with their sizes specified, or a single object of a fixed dimension that can be used repeatedly. Usually the packing ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
De Bruijn's Theorem
In a 1969 paper, Dutch mathematician Nicolaas Govert de Bruijn proved several results about packing congruent rectangular bricks (of any dimension) into larger rectangular boxes, in such a way that no space is left over. One of these results is now known as de Bruijn's theorem. According to this theorem, a "harmonic brick" (one in which each side length is a multiple of the next smaller side length) can only be packed into a box whose dimensions are multiples of the brick's dimensions.. Example De Bruijn was led to prove this result after his then-seven-year-old son, F. W. de Bruijn, was unable to pack bricks of dimension 1\cdot 2\cdot 4 into a 6\cdot 6\cdot 6 cube. The cube has a volume equal to that of 27 bricks, but only 26 bricks may be packed into it. One way to see this is to partition the cube into 27 smaller cubes of size 2\cdot 2\cdot 2 colored alternately black and white. This coloring has more unit cells of one color than of the other, but with this coloring any placemen ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Square Packing In A Square
Square packing in a square is a packing problem where the objective is to determine how many squares of side one (unit squares) can be packed into a square of side . If is an integer, the answer is , but the precise, or even asymptotic, amount of wasted space for non-integer is an open question. Small numbers of squares The smallest value of a that allows the packing of n unit squares is known when n is a perfect square (in which case it is \sqrt), as well as for n=2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, and 48. For most of these numbers (with the exceptions only of 5 and 10), the packing is the natural one with axis-aligned squares, and a is \lceil\sqrt\,\rceil, where \lceil\,\ \rceil is the ceiling (round up) function. The figure shows the optimal packings for 5 and 10 squares, the two smallest numbers of squares for which the optimal packing involves tilted squares.. The smallest unresolved case involves packing 11 unit squares into a larger square. 11 unit s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circle Packing In A Rectangle
Circle packing in a square is a packing problem in recreational mathematics, where the aim is to pack unit circles into the smallest possible square. Equivalently, the problem is to arrange points in a unit square aiming to get the greatest minimal separation, , between points. To convert between these two formulations of the problem, the square side for unit circles will be . Solutions Solutions (not necessarily optimal) have been computed for every . Solutions up to are shown below. The obvious square packing is optimal for 1, 4, 9, 16, 25, and 36 circles (the six smallest square numbers), but ceases to be optimal for larger squares from 49 onwards. Circle packing in a rectangle Dense packings of circles in non-square rectangles have also been the subject of many investigations. See also *Square packing in a circle References [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximum Disjoint Set
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. Every set of non-overlapping shapes is an independent set in the intersection graph of the shapes. Therefore, the MDS problem is a special case of the maximum independent set (MIS) problem. Both problems are NP complete, but finding a MDS may be easier than finding a MIS in two respects: * For the general MIS problem, the best known exact algorithms are exponential. In some geometric intersection graphs, there are sub-exponential algorithms for finding a MDS. * The general MIS problem is hard to approximate and doesn't even have a constant-factor approximation. In some geometric intersection graphs, there are polynomial-time approximation schemes (PTAS) for finding a MDS. Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing. The MDS pro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Guillotine Cutting
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 (also called an edge-to-edge cut) is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine. Guillotine cutting is particularly common in the glass industry. Glass sheets are scored along horizontal and vertical lines, and then broken along these lines to obtain smaller panels. It is also useful for cutting steel plates, cutting of wood sheets to make furniture, and cutting of cardboard into boxes. There are various optimization problems related to guillotine cutting, such as: maximize the total area of the produced pieces, or their total value; minimize the amount of waste (unused parts) of the large sheet, or the total number of sheets. They have been studied in combinatorial geometry, operations research and industrial engineering. A re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-completeness
In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. # the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deter ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
3-partition 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: * The input to the problem is a multiset ''S'' of ''n'' = 3 positive integers. The sum of all integers is . * The output is whether or not there exists a partition of ''S'' into ''m'' triplets ''S''1, ''S''2, …, ''S''''m'' such that the sum of the numbers in each one is equal to ''T''. The ''S''1, ''S''2, …, ''S''''m'' must form a partition of ''S'' in the sense that they are disjoint and they cover ''S''. The 3-partition problem remains strongly NP-complete under the restriction that every integer in ''S'' is strictly between ''T''/4 and ''T''/2. Example # The set S = \ can be partitioned into the four sets \, \, \ , \, each of which sums to ''T'' = 90. # The set S = \ can be partitioned into the two sets \, \ each of which sum to ''T'' = 15. # (every i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Orthogonality
In mathematics, orthogonality is the generalization of the geometric notion of ''perpendicularity''. By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in other fields including art and chemistry. Etymology The word comes from the Ancient Greek ('), meaning "upright", and ('), meaning "angle". The Ancient Greek (') and Classical Latin ' originally denoted a rectangle. Later, they came to mean a right triangle. In the 12th century, the post-classical Latin word ''orthogonalis'' came to mean a right angle or something related to a right angle. Mathematics Physics * In optics, polarization states are said to be orthogonal when they propagate independently of each other, as in vertical and horizontal linear polarization or right- and left-handed circular polarization. * In special relativity, a time axis determined by a rapidity of motion is hyperbolic-orthogonal to a space axis of simu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Strongly NP-hard
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. A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains NP-complete even when all of its numerical parameters are bounded by a polynomial in the length of the input. A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it; in combinatorial optimization, particularly, the phrase "strongly NP-hard" is reserved for problems that are not known to have a polynomial reduction to another strongly NP-complete problem. Normally numerical parameters to a problem are given in positional notation, so a prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.svg "Click for more on -> Packing Problems")
