スクエアパッキング

正方形パッキングは、より大きな形状（通常は正方形または円）に、同形の正方形をいくつ詰め込める かを決定することを目的とするパッキング問題です。

広場で

正方形への詰め込みとは、一辺の長さが であるより大きな正方形の中に詰め込むことができる単位正方形（一辺の長さが である正方形）の最大数を決定する問題である。 が整数 の場合、答えは であるが、任意の非整数の場合の未充填空間の正確な量、あるいは漸近的な量は未解決の問題である。^{[ 1 ]} ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a^{2},}$ ${\displaystyle a}$

辺の長さが1平方メートルの正方形に5つの単位正方形 ${\displaystyle 2+1/{\sqrt {2}}\approx 2.707}$

辺の長さが10の正方形 ${\displaystyle 3+1/{\sqrt {2}}\approx 3.707}$

辺の長さが11の正方形 ${\displaystyle a\approx 3.877084}$

単位正方形のパッキングを可能にするの最小値は、 が完全な正方形のとき（この場合は）として知られており、2、3、5、6、7、8、10、13、14、15、24、34、35、46、47、48 についても知られています。これらの数のほとんど（5 と 10 のみ例外）では、軸に沿った正方形のパッキングは自然なパッキングであり、 です。ここでは天井（切り上げ）関数です。^{[ 2 ] [ 3 ]}図は、5 と 10 の正方形 の最適パッキングを示しています。これらは、最適なパッキングが傾斜した正方形を含む最小の 2 つの正方形の数です。^{[ 4 ] [ 5 ]} ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n={}}$ ${\displaystyle a}$ ${\displaystyle \lceil {\sqrt {n}}\,\rceil }$ ${\displaystyle \lceil \,\ \rceil }$

未解決の最小のケースは である。11個の単位正方形を 未満の辺の長さの正方形に詰め込むことはできないことが知られている。対照的に、11個の正方形を最も密に詰め込んだ既知のケースは、ウォルター・トランプによって発見された、辺の長さが約3.877084の正方形の内側である。^{[ 4 ] [ 6 ]} ${\displaystyle n=11}$ ${\displaystyle \textstyle 2+{\frac {4}{\sqrt {5}}}\approx 3.789}$

最もよく知られている3つの異なる角度の正方形の詰め方における最小の例は である。これは1998年にハワイ大学の学部生ジョン・ビッドウェルによって発見され、辺の長さは である。^{[ 4 ]} ${\displaystyle n=17}$ ${\displaystyle a\approx 4.6756}$

以下は までの値に対する最小解であるが、この問題は未解決のままである: ^{[ 7 ]} ${\displaystyle n=12}$ ${\displaystyle n=11}$

単位正方形の数 ${\displaystyle n}$	大きな正方形の 最小の辺の長さ ${\displaystyle a}$
1	1
2	2
3	2
4	2
5	2.707...	${\displaystyle 2+{\frac {\sqrt {2}}{2}}}$
6	3
7	3
8	3
9	3
10	3.707...	${\displaystyle 3+{\frac {\sqrt {2}}{2}}}$
11	3.877…？
12	4

漸近的結果

数学における未解決問題

半整数の正方形における正方形パッキングの無駄なスペースの漸近的増加率はどれくらいですか?

数学におけるさらなる未解決問題

切り裂かれたチェス盤、n ² − 2マスの最適な詰め方

辺の長さ の値がより大きい場合、正方形を詰め込むことができる単位正方形の正確な数は不明です。軸に沿った単位正方形のグリッドを詰め込むことは常に可能ですが、これにより、約 の大きな領域が覆われずに無駄になる可能性があります。^{[ 4 ]} 代わりに、ポール・エルデシュとロナルド・グラハムは、傾斜した単位正方形による異なる詰め込みでは、無駄なスペースを（ここでは小さな o 記法で書く）まで大幅に削減できることを示しました。 ^{[ 8 ]} その後、グラハムとファン・チュンは、無駄なスペースを までさらに削減しました。^{[ 9 ]} しかし、クラウス・ロスとボブ・ヴォーンがを証明したように、すべての解法では少なくとも のスペースが無駄になります。特に、が半整数のとき、無駄なスペースは少なくともその平方根に比例します。^{[ 10 ]}無駄なスペースの正確な漸近的増加率は、辺の長さが半整数であっても、^未解決の問題です。^{[ 1} ${\displaystyle a}$ ${\displaystyle a\times a}$ ${\displaystyle \lfloor a\rfloor \!\times \!\lfloor a\rfloor }$ ${\displaystyle 2a(a-\lfloor a\rfloor )}$ ${\displaystyle o(a^{7/11})}$ ${\displaystyle O(a^{3/5})}$ ${\displaystyle \Omega {\bigl (}a^{1/2}(a-\lfloor a\rfloor ){\bigr )}}$ ${\displaystyle a}$

単位正方形の詰め込みにおいて、最適な個数とは決して言えない。特に、ある大きさの正方形に単位正方形を詰め込むことが可能な場合、必ず となり 、単位正方形を詰め込むことも可能となる。^{[ 2 ]} ${\displaystyle a\times a}$ ${\displaystyle n^{2}-2}$ ${\displaystyle a\geq n}$ ${\displaystyle n^{2}}$

円になって

円周上の正方形詰めは、n個の単位正方形を半径が可能な限り小さい円周上に詰めるという関連問題である。この問題では、 nが35まで良好な解が知られている。以下は、nが35までの既知の最小解である（ただし、最適解として知られているのはnとnの場合のみである）。^{[ 11 ]} ${\displaystyle n=12}$ ${\displaystyle n=1}$ ${\displaystyle n=2}$

正方形の数	円の半径
1	${\displaystyle {\sqrt {2}}/2\approx 0.707\ldots }$
2	${\displaystyle {\sqrt {5}}/2\approx 1.118\ldots }$
3	${\displaystyle 5{\sqrt {17}}/16\approx 1.288\ldots }$
4	${\displaystyle {\sqrt {2}}\approx 1.414\ldots }$
5	${\displaystyle {\sqrt {10}}/2\approx 1.581\ldots }$
6	1.688...
7	${\displaystyle {\sqrt {13}}/2\approx 1.802\ldots }$
8	1.978...
9	${\displaystyle {\sqrt {1105}}/16\approx 2.077\ldots }$
10	${\displaystyle 3{\sqrt {2}}/2\approx 2.121\ldots }$
11	2.214...
12	${\displaystyle {\sqrt {5}}\approx 2.236\ldots }$

他の形では

正方形を他の図形に詰め込むことは計算量が非常に多い場合がある。与えられた数の軸平行な単位正方形が与えられた多角形に収まるかどうかをテストすることはNP完全である。これは、直交凸多角形（穴のない多角形）で、軸平行な辺を持ち、頂点座標が半整数である場合でもNP完全である。^{[ 12 ]}

参照

• 正方形内の円充填
• 正方形を正方形にする
• 長方形パッキング
• ソファの移動問題

参考文献

1. ブラス、ピーター; モーザー、ウィリアム;パック、ヤーノシュ(2005) 『離散幾何学における研究問題』ニューヨーク: シュプリンガー、p. 45、ISBN 978-0387-23815-9, LCCN  2005924022 , MR  2163782
2. Kearney, Michael J.; Shiu, Peter (2002)、「単位正方形の正方形内への効率的なパッキング」、Electronic Journal of Combinatorics、9 (1)、研究論​​文14、14 pp.、doi : 10.37236/1631、MR 1912796、2011年6月4日時点のオリジナルからアーカイブ、2011年6月1日取得 
3. Bentz, Wolfram (2010)、「正方形内の13および46単位正方形の最適パッキング」、The Electronic Journal of Combinatorics、17 (R126)、arXiv : 1606.03746、doi : 10.37236/398、MR 2729375 
4. Friedman, Erich (2009), "Packing unit squares in squares: a survey and new results" , Electronic Journal of Combinatorics , 1000 , Dynamic Survey 7, doi : 10.37236/28 , MR 1668055 , 2018年2月24日時点のオリジナルよりアーカイブ, 2018年2月23日取得 
5. Stromquist, Walter (2003)、「10または11単位正方形を正方形に詰める」、Electronic Journal of Combinatorics、10、研究論文8、doi : 10.37236/1701、MR 2386538、2011年6月4日時点のオリジナルよりアーカイブ、2011年6月1日取得 
6. Friedman (2009)の2000年版では、この辺の長さは3.8772と記載されています。ここでより厳密な上限は、 Gensane, Thierry、Ryckelynck, Philippe (2005)「Improved dense packings of congruent squares in a square」、Discrete & Computational Geometry、34 (1): 97– 109、doi : 10.1007/s00454-004-1129-z、MR 2140885によるものです。 
7. Weisstein, Eric W.、「スクエアパッキング」、MathWorld
8. Erdős, P. ; Graham, RL (1975)、「等しい正方形による正方形の詰め込みについて」（PDF）、Journal of Combinatorial Theory、Series A、19：119–123、doi：10.1016/0097-3165(75)90099-0、MR 0370368 
9. Chung, Fan ; Graham, Ron (2020) 「大きな正方形における単位正方形の効率的なパッキング」（PDF）、離散幾何学と計算幾何学、64（3）：690– 699、doi：10.1007/s00454-019-00088-9
10. Roth, KF ; Vaughan, RC (1978)、「単位正方形による正方形のパッキングの非効率性」、Journal of Combinatorial Theory、シリーズA、24 (2): 170– 186、doi : 10.1016/0097-3165(78)90005-5、MR 0487806 
11. フリードマン、エリック、円の中の四角形
12. Abrahamsen, Mikkel; Stade, Jack (2024)、「単位正方形による単純多角形のパッキング、被覆、分割の困難さ」、第65回IEEE年次シンポジウム、コンピュータサイエンスの基礎、FOCS 2024、シカゴ、イリノイ州、米国、2024年10月27～30日、IEEE、pp.  1355～ 1371、arXiv : 2404.09835、doi : 10.1109/FOCS61266.2024.00087

外部リンク

• フリードマン、エリック、「Squares in Squares」、Github、Erich's Packing Center

「 https://en.wikipedia.org/w/index.php?title=Square_packing&oldid=1319483192」より取得