Packing problems: Difference between revisions

Revision as of 06:12, 27 April 2022

Revision as of 22:26, 29 April 2022

Line 71:

[[Image:Disk pack10.svg|thumb|120px|right|The optimal packing of 10 circles in a circle]]Many variants of 2-dimensional packing problems have been studied. See the linked pages for more information.

=== [[Circle packing|Packing of circles]] ===

{{main article|Circle packing}}

You are given ''n'' [[unit circle]]s, and have to pack them in the smallest possible container. Several kinds of containers have been studied:

You are given ''{{mvar|n''}} [[unit circle]]s, and have to pack them in the smallest possible container. Several kinds of containers have been studied:

* [[Circle packing in a circle|Packing circles in a '''circle''']] - closely related to spreading points in a unit circle with the objective of finding the greatest minimal separation, ''d''_''n'', between points. Optimal solutions have been proven for ''n'' ≤ 13, and ''n'' = 19.

* [[Circle packing in a square|Packing circles in a '''square''']] - closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, ''d''_''n'', between points. To convert between these two formulations of the problem, the square side for unit circles will be ''L'' = 2 + 2/''d''_''n''. [[File:15 circles in a square.svg|thumb|120px|right|The optimal packing of 15 circles in a square]]Optimal solutions have been proven for ''n'' ≤ 30.

* [[Circle packing in ana isosceles right trianglecircle|Packing circles in ana '''isosceles right trianglecircle''']] - goodclosely estimatesrelated areto knownspreading points in a unit circle with the objective of finding the greatest minimal separation, {{mvar|d{{sub|n}}}}, between points. Optimal solutions have been proven for {{math|''n'' ≤ 13}}, and {{math|1=''n'' <= 30019}}.

* [[Circle packing in a circlesquare|Packing circles in a '''circlesquare''']] - closely related to spreading points in a unit circlesquare with the objective of finding the greatest minimal separation, ''{{mvar|d''<{{sub>''|n''</sub>}}}}, between points. To convert between these two formulations of the problem, the square side for unit circles will be <math>L = 2 + 2/d_n</math>. [[File:15 circles in a square.svg|thumb|120px|right|The optimal packing of 15 circles in a square]]Optimal solutions have been proven for {{math|''n''&nbsp; ≤&nbsp;13, and&nbsp;''n''&nbsp;=&nbsp;1930}}.

* [[Circle packing in an equilateral triangle|Packing circles in an '''equilateral triangle''']] - Optimal solutions are known for ''n'' < 13, and [[conjecture]]s are available for ''n''&nbsp;<&nbsp;28.<ref>{{Cite journal | last1 = Melissen | first1 = J. | title = Packing 16, 17 or 18 circles in an equilateral triangle | journal = Discrete Mathematics | volume = 145 | issue = 1–3 | pages = 333–342 | year = 1995 | doi = 10.1016/0012-365X(95)90139-C| url = https://research.utwente.nl/en/publications/packing-16-17-of-18-circles-in-an-equilateral-triangle(b2172f19-9654-4ff1-9af4-59da1b6bef3d).html }}</ref>

* [[Circle packing in an isosceles right triangle|Packing circles in an '''isosceles right triangle''']] - good estimates are known for {{math|''n'' < 300}}.

* [[Circle packing in an equilateral triangle|Packing circles in an '''equilateral triangle''']] - Optimal solutions are known for {{math|''n'' < 13}}, and [[conjecture]]s are available for {{math|''n''&nbsp; <&nbsp; 28}}.<ref>{{Cite journal | last1 = Melissen | first1 = J. | title = Packing 16, 17 or 18 circles in an equilateral triangle | journal = Discrete Mathematics | volume = 145 | issue = 1–3 | pages = 333–342 | year = 1995 | doi = 10.1016/0012-365X(95)90139-C| url = https://research.utwente.nl/en/publications/packing-16-17-of-18-circles-in-an-equilateral-triangle(b2172f19-9654-4ff1-9af4-59da1b6bef3d).html }}</ref>

{{Anchor|Packing squares}}

=== Packing of squares ===

You are given ''{{mvar|n''}} [[unit square]]s and have to pack them into the smallest possible container, where the container type varies:

* [[Square packing in a square|Packing squares in a '''square''']]: Optimal solutions have been proven for ''{{mvar|n''&nbsp;=&nbsp;1–10}} from 1-10, 14–1614-16, 22–2522-25, 33–3633-36, 62–6462-64, 79–8179-81, 98–10098-100, and any [[square number|square]] [[integer]]. The wasted space is asymptotically {{math|[[Big O notation|O]](''a''<{{sup>|7/11</sup>}})}}.

* [[Square packing in a circle|Packing squares in a '''circle''']]: Good solutions are known for {{math|''n'' up to≤ 35}}.[[Image:10 kvadratoj en kvadrato.svg|thumb|120px|right|The optimal packing of 10 squares in a square]]

===[[Rectangle packing|Packing of rectangles]]===

{{main article|Rectangle packing}}

* '''Packing identical rectangles in a rectangle''': The problem of packing multiple instances of a single [[rectangle]] of size {{math|(''l'',''w'')}}, allowing for 90° rotation, in a bigger rectangle of size {{math|(''L'',''W''&hairsp;&hairsp; )}} has some applications such as loading of boxes on pallets and, specifically, [[woodpulp]] stowage. For example, it is possible to pack 147 rectangles of size (137,95) in a rectangle of size (1600,1230).

* '''Packing different rectangles in a rectangle''': The problem of packing multiple rectangles of varying widths and heights in an enclosing rectangle of minimum [[area]] (but with no boundaries on the enclosing rectangle's width or height) 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.