직각이등변삼각형에 원 채우기

직각이등변삼각형에 원 채우기는 가장 작은 직각이등변삼각형을 n 개의 단위원으로 채우는 채우기 문제이다.

최소해(길이는 빗변의 길이이다)를 아래의 표에 나타냈다.^[1] 직각이등변삼각형안에 n개의 점들간의 최소거리를 최대화하는 문제의 해와 같은 최적해는 n< 8일 때 최적임이 증명되었다.^[2] In 2011년에 heuristic 알고리즘이 이전에 최적이라고 알려진 해에서 18개의 개선점을 찾아냈으며, 그 중 가장 작은 것은 n=13일 때이다.^[3]

원의 개수	길이
1	$2+{\sqrt {2}}$ = 3.414...
2	$2+2{\sqrt {2}}$ = 4.828...
3	$4+{\sqrt {2}}$ = 5.414...
4	$2+3{\sqrt {2}}$ = 6.242...
5	$4+{\sqrt {2}}+{\sqrt {3}}$ = 7.146...
6	$6+{\sqrt {2}}$ = 7.414...
7	$4+{\sqrt {2}}+{\sqrt {2+4{\sqrt {2}}}}$ = 8.181...
8	$2+3{\sqrt {2}}+{\sqrt {6}}$ = 8.692...
9	$2+5{\sqrt {2}}$ = 9.071...
10	$8+{\sqrt {2}}$ = 9.414...
11	$5+3{\sqrt {2}}+{\dfrac {1}{3}}{\sqrt {6}}$ = 10.059...
12	10.422...
13	10.798...
14	$2+3{\sqrt {2}}+2{\sqrt {6}}$ = 11.141...
15	$10+{\sqrt {2}}$ = 11.414...

참조[편집]

↑ Specht, Eckard (2011년 3월 11일). “The best known packings of equal circles in an isosceles right triangle”. 2011년 5월 1일에 확인함.
↑ Xu, Y. (1996). “On the minimum distance determined by n (≤ 7) points in an isoscele right triangle”. 《Acta Mathematicae Applicatae Sinica》 12 (2): 169–175. doi:10.1007/BF02007736.
↑ López, C. O.; Beasley, J. E. (2011). “A heuristic for the circle packing problem with a variety of containers”. 《European Journal of Operational Research》 214 (3): 512. doi:10.1016/j.ejor.2011.04.024.

[1] Specht, Eckard (2011년 3월 11일). “The best known packings of equal circles in an isosceles right triangle”. 2011년 5월 1일에 확인함.

[2] Xu, Y. (1996). “On the minimum distance determined by n (≤ 7) points in an isoscele right triangle”. 《Acta Mathematicae Applicatae Sinica》 12 (2): 169–175. doi:10.1007/BF02007736.

[3] López, C. O.; Beasley, J. E. (2011). “A heuristic for the circle packing problem with a variety of containers”. 《European Journal of Operational Research》 214 (3): 512. doi:10.1016/j.ejor.2011.04.024.

[1]

[2]

[3]