볼록 껍질 (Convex Hull)

한 줄 정의: 주어진 점들을 모두 포함하는 가장 작은 볼록집합입니다.

쉽게 풀면

판에 못을 여러 개 박고 고무줄을 크게 벌려 바깥에서 놓으면, 고무줄이 바깥쪽 못들에 걸려 다각형 모양으로 조여집니다. 이 다각형이 볼록 껍질입니다. 수학적으로는 주어진 점들의 모든 볼록결합을 모은 집합이며, 그 점들을 담는 볼록집합 중 가장 작은 것입니다.

왜 중요한가

최적화에서 실현가능 영역을 볼록 껍질로 바꾸면 선형계획법으로 다룰 수 있게 되어 계산이 훨씬 쉬워집니다. 계산기하학에서는 충돌 검사, 도형 단순화, 군집 경계 추정의 기본 연산이며, 통계에서는 다변량 자료의 외곽선을 정의하는 데 쓰입니다.

논문에서는 이렇게 쓰입니다

"관측점들의 볼록 껍질을 계산하여 서식 범위의 외곽 경계를 추정하였다."

조금 더 깊게 보면

평면에서 n개의 점의 볼록 껍질은 그레이엄 스캔이나 분할정복 방식으로 n log n 시간에 계산할 수 있습니다. 카라테오도리 정리는 d차원에서 볼록 껍질의 어떤 점도 최대 d+1개의 원래 점의 볼록결합으로 표현된다는 것을 보장하여, 표현의 복잡도를 제한해 줍니다. 유한개의 점의 볼록 껍질은 볼록다면체가 되며, 꼭짓점 표현과 부등식 표현 사이의 변환 문제가 선형계획법 이론의 핵심입니다.

주의할 점

볼록 껍질은 점들을 감싸는 여러 경계 중 볼록한 것들 중 최소일 뿐, 실제 자료 분포의 오목한 모양을 반영하지 못합니다. 오목한 형태가 필요한 경우에는 알파 셰이프 같은 다른 방법을 써야 합니다.