| Packing Problem |
Article Index for Packing |
Website Links For Packing |
Information AboutPacking Problem |
| CATEGORIES ABOUT PACKING PROBLEM | |
| discrete geometry | |
| tiling puzzles | |
|
In a packing problem, you are given:
Usually the packing must be without gaps or overlaps, but in some packing problems the overlapping (of goods with each other and/or with the boundary of the container) is allowed but should be minimised. In others, gaps are allowed, but overlaps are not (usually the total area of gaps has to be minimised). PROBLEMS One classic problem is to fit as many Circle s of 1 cm Diameter as possible into a strip of dimensions 2 cm × ''n'', where ''n'' is any integer greater than or equal to zero. At least 2''n'' circles can fit (side by side, in perfect rows) but the solution is that if ''n'' > 63, then at least one more circle can fit than the formula 2''n'' suggests . In fact, for every added length of 64, an additional circle can fit . Another classic problem is the Sphere Packing problem, where one must determine how many Spherical objects of given diameter ''d'' can you pack into a box of size ''a'' × ''b'' × ''c''. This is one of the hardest problems in this category . A less classic problem is the square packing problem, where one must determine how many Square s of side 1 you can pack into a square of side ''a''. Obviously, here if ''a'' is an integer, the answer is ''a''2, but the precise, or even Asymptotic , answer for ''a'' a non-integer is open. Known results: :If you can pack ''n''2-2 squares in a square of side ''a'', then ''a'' ≥ ''n''. :The naive approach leaves wasted space of less than 2''a''+1. :The wasted space is asymptotically O (''a''7/11). :The wasted space not asymptotically O (''a''1/2). PUZZLES A classic puzzle of this kind is Pentomino , where the task is to arrange all twelve pentominoes into rectangles sized 3×20, 4×15, 5×12 or 6×10, respectively. SEE ALSO EXTERNAL LINKS Many puzzle books as well as mathematical journals contain articles on packing problems.
REFERENCES
|
|
|