구 채우기

구 채우기는 포탄을 쌓는 것과 같이 실제 적용 사례를 찾을 수 있다. 기하학에서 **구 채우기**(sphere packing)는 담는 공간 안에 겹치지 않는 구를 배열하는 것이다. 고려되는 구는 일반적으로 모두 동일한 크기이며, 공간은 일반적으로 3-차원 유클리드 공간이다. 그러나 구 채우기 문제는 크기가 다른 구, 다른 차원의 공간(2차원에서는 원 채우기 문제 또는 고차원에서는 초구 채우기 문제) 또는 쌍곡공간과 같은 비유클리드 공간을 고려하도록 일반화될 수 있다. 전형적인 구 채우기 문제는 구가 가능한 한 많은 공간을 채우는 배열을 찾는 것이다. 구가 채운 공간의 비율을 배열의 채우기 밀도라고 한다. 무한 공간에서 채우기의 국소 밀도는 측정되는 부피에 따라 달라질 수 있으므로, 문제는 일반적으로 충분히 큰 부피에 걸쳐 측정된 평균 또는 점근적 밀도를 최대화하는 것이다. 3차원에서 동일한 구의 가장 조밀한 채우기는 부피의 약 74%를 사용한다. 동일한 구의 무작위 채우기는 일반적으로 약 63.5%의 밀도를 갖는다.doi=10.1023/A:1023597707363
# 분류 및 용어
**격자** 배열(일반적으로 **정규** 배열이라고 함)은 격자의 점들이 매우 대칭적인 패턴을 형성하여 n-차원 유클리드 공간에서 n개의 벡터만으로 정의될 수 있는 배열이다. 격자 배열은 주기적이며, 격자를 번역(이동)하여 한 점이 다른 점이 있던 자리에 놓일 때 배열이 이전과 동일하다는 속성을 갖는다. 점들이 격자를 형성하지 않는 배열도 주기적일 수 있지만, **비주기적**일 수도 있으며, 이는 **무작위** 배열을 포함한다. 격자 채우기는 대칭 정도가 높기 때문에 격자가 아닌 채우기보다 분류하기가 더 쉽다. 주기적인 격자는 잘 정의된 밀도를 갖는다.
# 정규 채우기
평면에서 동일한 구의 정규 배열이 크기가 다른 구(거품)의 불규칙 배열로 변하는 모습. HCP 배열(왼쪽)과 FCC 격자(오른쪽)는 가장 흔한 두 가지 최고 밀도 배열이다. 구로 만든 세 평면을 쌓는 두 가지 방법
## 조밀 채우기
동일한 구의 조밀 채우기 3차원 유클리드 공간에서 동일한 구의 가장 조밀한 채우기는 조밀 채우기 구조라고 불리는 구조군에 의해 달성된다. 이러한 구조를 생성하는 한 가지 방법은 다음과 같다. 평면 위에 구가 조밀하게 배열된 것을 고려한다. 이를 A라고 부른다. 세 개의 이웃한 구에 대해, 네 번째 구를 세 개의 아래쪽 구 사이의 빈 공간에 위에 놓을 수 있다. 만약 첫 번째 평면 위의 두 번째 평면에서 구멍의 절반에 대해 이 작업을 수행하면, 새로운 조밀층이 생성된다. 이 작업을 수행하는 데는 B와 C라는 두 가지 가능한 선택이 있다. B를 선택했다고 가정하자. 그러면 B의 빈 공간의 절반은 A의 구의 중심 위에 놓이고, 나머지 절반은 B에 사용되지 않은 A의 빈 공간 위에 놓인다. 따라서 세 번째 층의 구는 첫 번째 층의 구 바로 위에 놓이거나, 두 번째 층이 차지하지 않은 첫 번째 층의 구멍 위에 놓일 수 있으며, 이는 각각 A형 층 또는 C형 층을 생성한다. A, B, C형 층을 결합하면 다양한 조밀 채우기 구조가 생성된다. 조밀 채우기 군 내의 두 가지 간단한 배열은 정규 배열에 해당한다. 하나는 입방 조밀 채우기(또는 면심 입방, "FCC", 이는 격자이다)라고 불리며, 층은 ABCABC... 순서로 번갈아 나타난다. 다른 하나는 육방 조밀 채우기("HCP", 이는 정규 배열이지만 격자는 아니다)라고 불리며, 층은 ABAB... 순서로 번갈아 나타난다. 그러나 많은 층 쌓기 순서가 가능하며(ABAC, ABCBA, ABCBAC 등), 여전히 조밀 채우기 구조를 생성한다. 이 모든 배열에서 각 구는 12개의 이웃한 구와 접촉하며,hdl=1959.4/unsworks_66615 평균 밀도는 다음과 같다. : \frac{\pi}{3\sqrt{2 \approx 0.74048. 1611년에 요하네스 케플러는 이것이 정규 및 불규칙 배열 모두에서 가능한 최대 밀도라고 추측했는데, 이는 케플러의 추측으로 알려졌다. 카를 프리드리히 가우스는 1831년에 이러한 채우기가 가능한 모든 격자 채우기 중에서 가장 높은 밀도를 갖는다는 것을 증명했다.year=1831 1998년에 토머스 캘리스터 헤일스는 1953년 라슬로 페제시 토트가 제안한 접근 방식을 따라 케플러의 추측에 대한 증명을 발표했다. 헤일스의 증명은 복잡한 컴퓨터 계산을 사용하여 많은 개별 사례를 확인하는 철저한 증명이다. 심사위원들은 헤일스의 증명의 정확성에 대해 "99% 확신한다"고 말했다. 2014년 8월 10일, 헤일스는 자동화된 증명 검증을 사용한 형식적인 증명을 완료했다고 발표하며 모든 의심을 없앴다.title=Long-term storage for Google Code Project Hosting
## 기타 일반적인 격자 채우기
물리 시스템에서 종종 발견되는 다른 격자 채우기가 있다. 여기에는 밀도 0.5236인 입방 격자, 밀도 0.6046인 육방 배열, 밀도 0.3401인 사면체 배열이 포함된다.url=http://mathworld.wolfram.com/SpherePacking.html
## 낮은 밀도의 잼 채우기
모든 구가 이웃에 의해 한 위치에 고정되는 채우기를 강체 또는 잼이라고 한다. 가장 낮은 밀도를 가진 것으로 알려진 엄격하게 잼된(유한 시스템에서도 기계적으로 안정적인) 정규 구 채우기는 밀도가 2/9 ≈ 0.49365에 불과한 희석된("터널링된") FCC 결정이다.bibcode = 2007JAP...102i3511T 가장 느슨한 것으로 알려진 정규 잼된 채우기는 약 0.555의 밀도를 갖는다.bibcode=2010SMat....6.2925F
# 불규칙 채우기
무작위 조밀 채우기 구들을 조밀하게 채우려고 하면 항상 세 개의 채워진 구 사이의 빈 공간에 다음 구를 놓으려는 유혹을 받는다. 이 방식으로 다섯 개의 구를 조립하면 위에서 설명한 정규 채우기 배열 중 하나와 일치할 것이다. 그러나 이 방식으로 여섯 번째 구를 놓으면 구조가 어떤 정규 배열과도 일치하지 않게 된다. 이로 인해 압축에 대해 안정적인 무작위 조밀 채우기가 가능해진다.bibcode = 2007PhT....60f...8C 무작위 느슨한 채우기를 진동시키면 구형 입자가 정규 채우기로 배열될 수 있으며, 이 과정을 알갱이 결정화라고 한다. 이러한 과정은 구형 알갱이를 담는 용기의 기하학적 구조에 따라 달라진다. 구들이 용기에 무작위로 추가된 다음 압축되면, 더 이상 압축될 수 없을 때 일반적으로 "불규칙" 또는 "잼된" 채우기 구성으로 알려진 것을 형성한다. 이 불규칙 채우기는 일반적으로 약 64%의 밀도를 갖는다. 최근 연구는 분석적으로 63.4%의 밀도 한계를 초과할 수 없다고 예측한다.arxiv = 0808.2196 이 상황은 1차원 또는 2차원 구(즉, 선분 또는 원) 컬렉션을 압축하면 정규 채우기가 생성되는 1차원 또는 2차원의 경우와는 다르다.
# 초구 채우기
2=1, 2, 3, 8, 24차원 외의 차원에서의 가장 조밀한 구 채우기는 무엇인가? 구 채우기 문제는 임의의 차원에서의 공 채우기 문제 중 3차원 버전이다. 2차원에서는 동등한 문제가 평면에서의 원 채우기이다. 1차원에서는 선분을 선형 우주에 채우는 것이다.bibcode = 1962Natur.196..764G 3차원보다 높은 차원에서 초구의 가장 조밀한 격자 채우기는 8차원과 24차원에서 알려져 있다.urlname=HyperspherePacking 불규칙 초구 채우기에 대해서는 거의 알려진 바가 없으며, 일부 차원에서는 가장 조밀한 채우기가 불규칙할 수도 있다. 이 추측에 대한 몇 가지 지지는 특정 차원(예: 10차원)에서 가장 조밀한 것으로 알려진 불규칙 채우기가 가장 조밀한 것으로 알려진 정규 채우기보다 더 조밀하다는 사실에서 비롯된다.arxiv=math/0207256 2016년, 마리나 뱌조우스카는 포장 밀도가 \tfrac{\pi^4}{2^4 4!}인 E8 격자가 8차원 공간에서 최적의 포장(규칙성에 관계없이)을 제공한다는 증명을 발표했다.hdl=21.11116/0000-0004-08A3-B 곧이어 그녀와 공동 연구자 그룹은 밀도가 \tfrac{\pi^{12{12!}인 리치 격자가 24차원에서 최적이라는 유사한 증명을 발표했다.doi=10.4007/annals.2017.185.3.8 이 결과는 이 두 격자가 최적에 매우 가깝다는 것을 보여주는 이전 방법을 바탕으로 개선한 것이다.arxiv = math.MG/0403263 arxiv = math.MG/0408174 새로운 증명은 신중하게 선택된 모듈러 함수의 라플라스 변환을 사용하여 회전대칭 함수 f를 구성하는 것을 포함하며, 이때 f와 그 푸리에 변환 f̂ 둘 다 원점에서 1이고, 최적 격자의 다른 모든 점에서 0이며, f는 채우기의 중심 구 바깥에서 음수이고 f̂는 양수이다. 그런 다음 f의 푸아송 합 공식을 사용하여 최적 격자의 밀도를 다른 채우기와 비교한다.publisher=프린스턴 고등연구소. 뱌조우스카의 공동 저자 중 한 명이 새로운 증명을 설명하는 한 시간짜리 강연 비디오. 증명이 공식적으로 심사되고 발표되기 전에, 수학자 피터 사르낙은 이 증명을 "놀랍도록 간단하다"고 부르며 "논문을 읽기 시작하면 이것이 옳다는 것을 알게 된다"고 썼다.date=30 March 2016 고차원에서 다른 연구 방향은 가장 조밀한 채우기의 밀도에 대한 점근적 경계를 찾는 것이다. 큰 n에 대해, n차원에서 가장 조밀한 격자는 cn ⋅ 2−n (일부 상수 c에 대해)와 2−(0.599+o(1))n 사이의 밀도 \theta(n)를 갖는 것으로 알려져 있다.arxiv=1611.01685 추측적 경계는 그 사이에 놓인다.mr=2264469 2023년 프리프린트에서 마르셀로 캄포스, 매튜 젠센, 마커스 미셸렌, 줄리안 사하스라부드헤는 최대 밀도의 하한을 \theta(n)\geq (1-o(1))\frac{n\ln n}{2^{n+1로 개선했다고 발표했다.eprint=2312.10026language=en 그들의 기술 중에는 뢰들 니블을 사용한다. 2025년 4월 프리프린트에서 보아즈 클라르타그는 \theta(n)\geq c\frac{n^2}{2^{n로 상당한 추가 개선을 발표했다.eprint=2504.05042access-date=2025-07-07 클라르타그는 그의 작업을 C.A. 로저스의 무작위 격자 인수의 확률적 진화적 적응으로 본다.
# 크기가 다른 구 채우기
year = 2011 화학 및 물리 과학의 많은 문제는 하나 이상의 크기의 구를 사용할 수 있는 채우기 문제와 관련될 수 있다. 여기서는 구를 조밀하게 채워진 동일한 구 영역으로 분리할지, 아니면 여러 크기의 구를 화합물 또는 틈새형 채우기로 결합할지 선택해야 한다. 여러 크기의 구(또는 분포)를 사용할 수 있는 경우 문제는 빠르게 해결하기 어려워지지만, 이진 단단한 구(두 가지 크기)에 대한 일부 연구는 가능하다. 두 번째 구가 첫 번째 구보다 훨씬 작을 때, 큰 구를 조밀하게 채우고, 작은 구를 팔면체 및 사면체 틈새에 배열하는 것이 가능하다. 이 틈새 채우기의 밀도는 반지름 비율에 매우 민감하게 의존하지만, 극단적인 크기 비율의 한계에서 작은 구는 큰 구가 공간을 채운 것과 동일한 밀도로 틈새를 채울 수 있다.bibcode = 1949JAP....20..154H 큰 구가 조밀하게 채워진 배열에 있지 않더라도, 큰 구 반지름의 최대 0.29099까지의 작은 구를 항상 삽입할 수 있다.doi-access = free 작은 구의 반지름이 큰 구 반지름의 0.41421보다 클 때, 더 이상 조밀 채우기 구조의 팔면체 구멍에도 들어갈 수 없다. 따라서 이 지점을 넘어서면 호스트 구조가 틈새를 수용하기 위해 확장되거나(이는 전체 밀도를 손상시킨다) 더 복잡한 결정성 화합물 구조로 재배열되어야 한다. 반지름 비율이 0.659786까지 조밀 채우기 밀도를 초과하는 구조가 알려져 있다.url=http://www.emis.de/journals/BAG/vol.51/no.2/3.html 이러한 이진 채우기에서 얻을 수 있는 밀도의 상한도 얻어졌다.article-number=e23 이온 결정과 같은 많은 화학적 상황에서 화학량론은 구성 이온의 전하에 의해 제한된다. 채우기에 대한 이 추가 제약은 상호 작용하는 전하의 쿨롱 에너지를 최소화해야 하는 필요성과 함께 다양한 최적 채우기 배열을 이끈다. 반지름이 임의로 주어졌을 때 엄격하게 잼된 구 채우기의 밀도 상한은 1이다. 이러한 구 채우기의 한 예는 아폴로니안 구 채우기이다. 이러한 구 채우기의 하한은 0이다. 한 예는 디오니소스 구 채우기이다.pmid=35061468
# 쌍곡 공간
원과 구의 개념은 쌍곡공간으로 확장될 수 있지만, 가장 조밀한 채우기를 찾는 것은 훨씬 더 어려워진다. 쌍곡 공간에서는 한 구를 둘러쌀 수 있는 구의 수에 제한이 없다(예를 들어, 포드 원은 각 원이 무한한 수의 다른 원으로 둘러싸인 동일한 쌍곡 원의 배열로 생각할 수 있다). 평균 밀도의 개념 또한 정확하게 정의하기 훨씬 더 어려워진다. 어떤 쌍곡 공간에서든 가장 조밀한 채우기는 거의 항상 불규칙하다.doi-access = free 이러한 어려움에도 불구하고 K. 뵈뢰츠키는 n ≥ 2인 쌍곡 n-공간의 구 채우기 밀도에 대한 일반적인 상한을 제시한다.year = 1978 3차원에서 뵈뢰츠키 상한은 약 u=%이며, 슐레플리 기호 3,3,6을 가진 6차 정사면체 벌집의 호로구 채우기에 의해 실현된다.issue = 1–2 이 구성 외에도 쌍곡 3차원에서 밀도 상한을 실현하는 최소 3가지 다른 호로구 채우기가 존재하는 것으로 알려져 있다.arxiv = 1007.0722
# 접촉하는 쌍, 삼중쌍, 사중쌍
단위 공의 임의의 유한 채우기의 접촉 그래프는 꼭짓점이 채우기 요소에 해당하고 해당 두 채우기 요소가 서로 접촉하면 두 꼭짓점이 에지로 연결되는 그래프이다. 접촉 그래프의 에지 집합의 카디널리티는 접촉하는 쌍의 수를 제공하고, 접촉 그래프의 3-사이클 수는 접촉하는 삼중쌍의 수를 제공하며, 접촉 그래프의 사면체 수는 접촉하는 사중쌍의 수를 제공한다 (일반적으로 n차원 구 채우기와 관련된 접촉 그래프의 경우 접촉 그래프의 n-단순체 집합의 카디널리티는 구 채우기에서 접촉하는 (n + 1)-튜플의 수를 제공한다). 3차원 유클리드 공간의 경우, 카롤리 베즈덱과 캘거리 대학교의 새뮤얼 리드가 접촉하는 쌍, 삼중쌍, 사중쌍의 수에 대한 비자명 상한doi=10.1007/s00022-013-0156-4을 증명했다. n개의 동일한 구 사이의 접촉점 수를 최대화하는 배열을 찾는 문제는 "끈적이는 구 문제"로 알려져 있다. 최대값은 n ≤ 11에 대해 알려져 있으며, 더 큰 n에 대해서는 추측 값만 알려져 있다.language=en
# 다른 공간
하이퍼큐브의 모서리에 구를 채우는 것(해밍 거리로 정의된 해밍 볼을 사용하는 경우)은 오류 수정 코드를 설계하는 것과 일치한다. 구의 반지름이 t이면 구의 중심은 (2t + 1)-오류 수정 코드의 코드워드가 된다. 격자 채우기는 선형 코드에 해당한다. 유클리드 구 채우기와 오류 수정 코드 사이에는 다른 더 미묘한 관계가 있다. 예를 들어, 이진 골레 부호는 24차원 리치 격자와 밀접하게 관련되어 있다. 이러한 연결에 대한 자세한 내용은 콘웨이와 슬론의 책 『구 채우기, 격자 및 그룹』을 참조하라.edition=3rd