Covering·Packing과 유한 Net

덮기와 분리는 서로 다른 질문

복잡한 연속 집합을 유한한 대표점으로 대신하려면 얼마나 많은 점이 필요할까요? Cover는 모든 대상을 가까운 대표점으로 덮고, packing은 서로 가까이 있지 않은 점을 많이 고릅니다. 먼저 거리, 덮을 집합, 허용할 중심, 부등식의 등호 여부를 정해야 합니다.

실습 대상은 반지름 1인 원 위 N개의 정다각형 꼭짓점입니다. 중심도 그 꼭짓점 중에서만 고릅니다. Cover는 거리 ≤ε, packing은 거리 >ε를 사용합니다. 연속 원의 빈 부분까지 덮는 문제는 아닙니다.

순환 간격을 거리로 바꾸기

k칸 떨어진 꼭짓점의 chord 거리는 2sin(πk/N)입니다. 양옆 r칸까지 ε 이하라면 한 중심은 L=min(N,2r+1)개를 덮습니다. 덮기 수는 적어도 ceil(N/L)이고, 원을 따라 L칸씩 이동한 중심들이 이를 달성합니다.

Packing은 인접한 선택점 사이 순환 간격이 최소 r+1이어야 합니다. 따라서 최대 개수는 floor(N/(r+1))이며, 이 간격으로 점을 선택해 달성합니다. 개수 1일 때는 쌍 거리의 최솟값을 정의하지 않아 —로 표시합니다.

열두 꼭짓점 예제

N=12,ε=.8이면 한 칸 거리는 약 .518, 두 칸은 1이므로 r=1입니다. 한 중심이 세 점을 덮어 중심 4개면 충분하고, 두 칸씩 분리하면 packing 6개입니다. 주황 채운 점은 cover, 고리는 packing입니다. 겹치는 위치는 동심 표식으로 표시하며 표에서도 두 선택을 확인할 수 있습니다.

ε=2이면 모든 꼭짓점을 한 중심으로 덮습니다. 원의 최대 거리가 2인데 packing은 엄밀히 2보다 커야 하므로 하나만 고릅니다. 경계에서 ≤와 >를 바꾸면 다른 문제입니다.

고차원 net으로 이어지는 이유

일반적인 고차원 증명에서는 각 대표점에서의 확률 상계에 union bound를 적용하고, 주변 점과의 오차를 연속성이나 Lipschitz 조건으로 제어합니다. 덮기 점이 많을수록 union bound 비용도 커집니다. 이 유한 원의 닫힌 개수를 고차원 단위 공의 covering number로 그대로 쓰면 안 됩니다. 차원·노름·집합과 중심 제약이 달라집니다.

확인 문제와 해설

1. ε=.1인 열두 꼭짓점의 cover 수는? 각자만 덮으므로 12입니다.
2. Cover와 packing이 같은 개수여야 하나요? 아니요. 목적과 부등식이 다릅니다.
3. 이 그림이 연속 원의 ε-cover를 증명하나요? 아니요. 유한 꼭짓점만 검사합니다.

추가 읽기: Vershynin, High-Dimensional Probability — publisher’s page.