채우기 문제
채우기 문제는 물체를 용기에 채우는 수학의 최적화 문제이다. 목표는 하나의 용기에 물체를 가능한한 빽빽하게 채우거나 모든 물체를 가능한한 적은 용기에 채우는 것이다. 이 문제의 대부분은 실생활에 포장, 저장 그리고 수송 문제와 관계지을 수 있다. 각 채우기 문제는 이중 덮기 문제가 있다. 이것은 겹치는 것을 허용하여 용기의 모든 영역을 동일한 물체로 완전히 덮는데 몇 개가 들어가는지를 구하는 문제이다.
상자 채우기 문제는 다음이 주어진다:
보통 채우기는 물건과 다른 물건 사이나 용기 벽 사이에 겹치는 일이 없어야 한다. 일부 변형에서 초점은 용기에 최대 밀도로 채우는 구성을 찾는 것이다. 더 일반적으로 목표는 가능한 적은 용기에 모든 물체를 담는 것이다. 어떤 변형에서 (물체와 물체간 그리고/또는 용기의 경계에서) 겹치는 것은 허락되지만 최소화되어야 한다.
이 문제의 대부분에서 용기의 크기가 모든 방향으로 커질 때 무한 유클리드 공간을 최대한 빽빽하게 채우는 문제와 같아진다. 이 문제는 많은 과학 분야와 관련이 있으며 중대한 관심을 받고 있다. 케플러의 추측은 구 채우기의 최적해를 몇백년 전에 제시되었고, 토머스 캘리스터 헤일즈(Thomas Callister Hales)가 증명했다. 타원체, 사면체를 포함한 플라톤과 아르키메데스 다면체와 불평등 구형 이합체와 같은 많은 모양들도 관심을 받았다.
이 문제는 수학적으로 원 채우기 정리의 아이디어와는 다르다. 관련된 원 채우기 문제는 평면이나 구의 표면에서 원의 크기가 다를 수 있는 원을 채우는 것을 다룬다.
다른 차원의 구는 일차원 보다 큰 차원에서 완벽히 효율적으로 채울 수 없다(일차원 우주에서, 원과 비슷한 것은 단지 두 점 뿐이다). 다시 말해, 원으로만 채울 때는 항상 사용하지 않은 공간이 있다. 원을 가장 효율적으로 채우는 방법인 육각형 채우기는 대략적으로 91%의 효율을 얻을 수 있다.
3차원에서 면심입방구조는 가장 좋은 격자 채우기이기 때문에 최적의 채우기라고 여겨진다. 3차원에서 '단순'한 구 채우기('단순' 은 조심스럽게 정의해야 한다)는 정의 가능한 9가지가 있다. 8차원 E8 격자와 24차원 리치 격자는 각각 실 차원 공간에서 최적으로 증명되었다.
정육면체는 3차원 공간을 완전히 채우도록 배열할 수 있다, 가장 자연스러운 채우기는 정육면체 벌집이다. 다른 정다면체는 공간을 스스로 채울 수 없지만 몇 가지 예비 결과가 알려져 있다. 정사면체는 적어도 85%의 채우기를 할 수 있다. 정십이면체의 최대 채우기는 앞에서 말한 면심 입방 격자(FCC)를 기반으로 한다.
정사면체와 정팔면체는 정사면체-정팔면체 벌집으로 알려진 배열로 공간을 채울 수 있다.
국소 발전 방법과 무작위 채우기를 결합한 시뮬레이션은 정이십면체, 정십이면체, 정팔면체에 대한 격자 채우기가 모든 채우기에서 최적이라는 것을 나타낸다.
주어진 입방체(3차원 직사각형)의 집합으로 채울 수 있는 최소 입방체 용기의 개수를 결정한다. 채우려는 육면체는 각 축을 기준으로 90도 회전시킬 수 있다.
formula_1개의 분리된 열린 단위 공으로 채울 수 있는 가장 작은 공을 찾는 문제는 formula_2이고 제한 없는 무한 차원의 힐베르트 공간에 있을 때, formula_3차원 유클리드 공간에서 간단하고 완벽한 답이 있다. 일반적인 문제의 취지를 밝히기 위해 자세히 설명할 필요가 있다. 이 경우에 formula_1쌍의 접하는 단위 공의 조합이 가능하다. 중심을 모서리가 2개인 formula_5차원 단체의 꼭짓점 formula_6에 두자; 이것은 쉽게 정규직교 기반에서 시작하는 것을 알 수 있다. 조금 계산해 보면, 무게중심에서 꼭짓점 까지의 거리는 formula_7이라는 것을 알 수 있다. 게다가, 공간의 다른 모든 점은 필연적으로 formula_1개의 정점 중 "적어도" 하나로부터 더 큰 거리를 갖는다. 공의 포함관계를 생각하면, formula_6를 중심으로 하는 formula_1개의 열린 단위 공은 이 조합에서 최소의 반경 formula_11을 갖는 원에 들어있다.
이 조합이 최적임을 보이기 위해서, 중심이 formula_12이고 반지름이 formula_13인 원 안에 있는 formula_1개의 분리된 열린 단위 공의 중심을 formula_15이라고 하자. 유한집합 formula_16에서 formula_17로 대응시키자. 모든 formula_18에 대해서 formula_19를 formula_20로 대응시키자. 모든 formula_21에 대해서 formula_22일 때 이 대응은 1-Lipschitz 이고, Kirszbraun 정리에 의해서 이는 전역적으로 정의된 1-Lipschitz 매핑으로 확장된다; 특히, 모든 formula_23에 대해서 formula_24이기 때문에 또한 formula_25인 점formula_26이 존재한다. 이것은 오직 formula_27일 때 만 formula_1개의 분리된 열린 단위 공들이 반지름이 formula_13인 공 안에 있을 수 있다는 것을 보여준다. 무한차원 힐베르트 공간에서 이것은 formula_30. 예를 들어, formula_31를 중심으로 가지고 formula_32은 정규 직교 기반인 단위 공은 원점을 중심으로 하고 반지름이 formula_33인 원에 분리되어서 포함되어있다. 게다가 formula_34일 때는 반지름이 formula_35인 공 안에 들어갈 수 있는 분리된 열린 단위 공의 최대 개수는 formula_36.
.의 크기를 가지는 직육면체에 지름 "d"인 구체가 몇 개가 들어갈 지를 결정한다.
반지름이 "R" 이고 반지름이 "r" (< "R")인 "n"개의 구가 들어갈 원기둥의 높이 "h"를 결정한다.
단위원 "n"개로 가장 작은 원을 채운다. 이것은 단위원에 점을 퍼뜨려 가장 큰 첨들간 최소거리 "d"를 찾는 문제와 매우 유사한 문제이다.
"n" ≤ 13일 때와 "n" = 19일 때 최적해가 증명되었다.
단위원 "n"개로 가장 작은 정사각형을 채운다. 이것은 단위원에 점을 퍼뜨려 가장 큰 첨들간 최소거리 "d"를 찾는 문제와 매우 유사한 문제이다. 이 두 문제를 변환하려면 단위 원이 있는 정사각형의 한 변의 길이는 "L" = 2 + 2/"d"이다.
"n" ≤ 30일 때 최적해가 증명되었다.
단위원 "n"개로" "가장 작은 직각이등변삼각형에 채운다. "n"<300일 때 좋은 근사가 알려져 있다.
단위원 "n"개로 가장 작은 정삼각형을 채운다. "n"<13일 때 최적해가 알려져 있고, "n" 정사각형에 넣는다.
최적해는 "n" = 1–10, 14–16, 22–25, 33–36, 62–64, 79–81, 98–100, 그리고 모든 사각수일 때 증명되었다.
낭비되는 공간은 점근적으로 O("a")이다.
정사각형 "n"개를 가능한 작은 원에 넣는다.
최소해:
크기가 ("l","w")인 직사각형 여러개를 90° 회전을 허용하여 크기가 ("L","W")인 큰 직사각형 안에 채우는 문제는 파렛트에 상자를 싣거나 특히 나무 펄프 보관 등의 적용이 있다.
예를 들어, 크기가 (137,95)인 직사각형 147개는 크기가 (1600,1230)인 직사각형을 채울 수 있다.
다양한 너비와 높이를 가지는 직사각형들을 최소 면적의 (하지만 둘러싸는 직사각형의 너비와 높이에는 경계가 없는) 직사각형에 채우는 문제는 이미지들을 하나의 큰 이미지로 결합할 때 중요한 문제이다. 각각의 이미지를 웹 서버에 요청하기 때문에, 하나의 큰 이미지를 로딩하는 웹 페이지는 같은 페이지에서 여러 작은 이미지를 로딩하는 브라우저보다 빠르다.
다양한 너비와 높이를 가지는 직사각형들을 최소넓이의 직사각형에 채우는 빠른 알고리즘의 예는 여기 있다.
타일링이나 테셀레이션 문제에서 틈이나 겹치는 것이 없어야한다. 이런 종류의 퍼즐의 대부분은 직사각형이나 폴리오미노를 큰 직사각형이나 사각형같은 모양에 채우는 문제와 관련되어있다.
직사각형(과 직육면체)를 직사각형 (직육면체)에 틈이나 겹침없는 타일링에 대해서는 상당히 많은 정리들이 있다:
폴리오미노 타일링 연구는 크게 두 종류의 문제로 나뉜다: 합동인 타일로 직사각형을 타일링 하고, 각 폴리오미노를 직사각형에 채운다.
두번째 종류의 고전 퍼즐은 펜토미노 12개 전부를 크기가 3×20, 4×15, 5×12 또는 6×10인 직사각형에 배열하는 것이다.
불규칙한 물체 채우기는 폐쇄적인 해결법에는 적합하지 않다; 하지만 실용 환경 과학에 적용은 매우 중요하다. 예를 들어, 불규칙한 모양의 흙 입자를 크기와 모양을 다양하게 채우기는 식물종의 뿌리 형성과 토양에서 물의 움직임에 중요하다.수학 잡지같이 많은 퍼즐 책은 채우기 문제를 포함하고 있다.