볼록 껍질

수치해석 컴퓨터 그래픽스 마지막 수정: 2026-08-17 04:12:41

1. 개요[편집]

볼록 껍질 Convex Hull
정의	주어진 집합을 포함하는 가장 작은 볼록집합
2D 최적 복잡도	O(n log h) — 출력 민감
하한	Ω(n log n) (정렬 환산), 출력 민감형은 Ω(n log h)
대표 알고리즘	그레이엄 스캔 · 모노톤 체인 · 자비 감싸기 · Chan · QuickHull
핵심 술어	방향 판정 orient2d / orient3d
쌍대·연결	지지함수 · 들로네 삼각분할 · GJK

볼록 껍질(convex hull)은 주어진 점 집합 $S$ 를 포함하는 가장 작은 볼록집합, 즉 $S$ 를 포함하는 모든 볼록집합의 교집합 $\mathrm{conv}(S)$ 다. 평면 위에 못을 박아 놓고 고무줄을 크게 벌려 놓았다가 놓으면 생기는 그 도형이 맞다. 유한 점 집합이면 결과는 볼록다각형(2D)·볼록다면체(3D)이고, 그 꼭짓점은 항상 원래 점들 중 일부다.

계산기하학에서 볼록 껍질이 유독 자주 불려 나오는 이유는 두 가지다. 첫째, 볼록성은 거의 모든 기하 알고리즘의 전제조건이다. GJK 알고리즘도, 지지함수 오라클도, 분리 초평면도 볼록체 위에서만 얌전히 돈다. 둘째, 볼록 껍질은 정렬의 기하 버전이라 알고리즘 설계의 표준 연습문제이자, 정렬처럼 다른 문제의 전처리로 끝없이 재활용된다. 지름·폭·최소 둘러싸는 사각형·들로네 삼각분할이 전부 껍질 위에서 혹은 껍질로 환산되어 풀린다.

2. 정의와 기본 성질[편집]

$\mathrm{conv}(S)$ 는 동치인 두 가지 방식으로 정의된다.

\mathrm{conv}(S) = \bigcap_{\substack{C \supseteq S \\ C\ \text{볼록}}} C = \Bigl\{\ \sum_{i=1}^{k}\lambda_i x_i \ :\ x_i \in S,\ \lambda_i \ge 0,\ \sum_i \lambda_i = 1 \Bigr\}

위가 “밖에서 조여 오는” 정의, 아래가 “안에서 채우는” 볼록결합 정의다. 카라테오도리 정리에 따르면 $\mathbb{R}^d$ 에서는 $k \le d+1$ 개의 점만으로 충분하다 — 평면 위의 어떤 점도 세 점의 볼록결합으로 쓸 수 있다는 뜻이고, 그래서 GJK가 심플렉스를 최대 삼각형·사면체까지만 키우면 된다.

유한 점 집합의 껍질에서 실제로 필요한 것은 극점(extreme point), 즉 다른 점들의 볼록결합으로 표현되지 않는 점들이다. 껍질의 꼭짓점 개수를 보통 $h$ 로 쓰는데, $h$ 는 $3$ 부터 $n$ 까지 아무 값이나 될 수 있다. 정규분포에서 뽑은 $n$ 개 점의 껍질 꼭짓점 수 기댓값이 $O(\sqrt{\log n})$ 정도라는 사실은 “출력 민감” 알고리즘이 실전에서 왜 그렇게 잘 먹히는지를 설명한다.¹

3. 2차원 알고리즘[편집]

평면 껍질 알고리즘은 계산기하 교과서의 첫 장을 통째로 차지한다. 다 같은 답을 내지만 성격이 다르다.

알고리즘	시간	발상
자비 감싸기(gift wrapping, 1973)	O(nh)	가장 왼쪽 점부터 “가장 덜 꺾이는” 다음 점을 매번 전수 탐색
그레이엄 스캔(1972)	O(n log n)	기준점 기준 편각 정렬 후 스택으로 우회전 제거
앤드루 모노톤 체인(1979)	O(n log n)	사전식 정렬 후 하부 껍질·상부 껍질을 따로 쌓기
QuickHull	평균 O(n log n), 최악 O(n²)	가장 먼 점으로 분할, 삼각형 내부 점을 통째 폐기
Chan(1996)	O(n log h)	그레이엄 스캔 + 자비 감싸기 하이브리드, 출력 크기 추측을 배가

그레이엄 스캔은 최저 $y$ 좌표 점을 기준으로 나머지를 편각 정렬한 뒤, 스택에 넣으며 “직전 두 점과 새 점이 우회전이면 직전 점을 버린다”를 반복한다. 정렬이 $O(n\log n)$ , 스캔이 $O(n)$ 이라 총 $O(n \log n)$ .

모노톤 체인은 실무에서 더 자주 쓰인다. 편각 정렬은 삼각함수나 조심스러운 사분면 분기가 필요하고 동일 편각 처리가 지저분한데, 사전식 정렬 $(x, y)$ 는 그냥 튜플 비교라서다. 정렬 후 왼쪽에서 오른쪽으로 훑어 하부 껍질을, 반대로 훑어 상부 껍질을 만들고 이어 붙이면 끝. 코드가 20줄이라 대회 코드북의 국룰이 됐다.

Chan의 알고리즘은 발상이 예쁘다. 껍질 크기 $h$ 를 $m$ 으로 추측하고, 점들을 크기 $m$ 짜리 $\lceil n/m \rceil$ 개 그룹으로 나눠 각각 그레이엄 스캔( $O(n\log m)$ )을 돌린다. 그다음 자비 감싸기를 도는데, 다음 접점을 전수 탐색하는 대신 각 소껍질에서 접선을 이진 탐색( $O(\log m)$ )으로 찾는다. $m$ 스텝 안에 껍질이 닫히면 성공, 아니면 $m \leftarrow m^2$ 으로 키워 재시작. $m = 2^{2^t}$ 로 배가하면 총비용이 마지막 시도에 지배되어 $O(n \log h)$ 가 된다. 커크패트릭-자이델(1986)의 “궁극의 평면 볼록껍질 알고리즘”이 같은 복잡도를 먼저 달성했지만, Chan 쪽이 훨씬 짧고 3차원으로도 그대로 올라간다.

4. 하한 — 왜 정렬보다 쉬울 수 없나[편집]

껍질을 구하는 비용의 하한은 $\Omega(n\log n)$ 이며, 증명은 한 줄이다. 실수 $x_1,\dots,x_n$ 을 정렬하고 싶다면 각각을 포물선 위의 점 $(x_i, x_i^2)$ 으로 올린다. 포물선은 볼록이므로 모든 점이 껍질 위에 있고, 껍질을 반시계 방향으로 읽으면 그게 곧 정렬된 순서다. 따라서 껍질을 $o(n\log n)$ 에 구하면 정렬도 그렇게 할 수 있고, 대수적 결정트리 모형에서 정렬의 하한이 $\Omega(n\log n)$ 이므로 모순.²

출력 민감 관점의 하한은 $\Omega(n \log h)$ 이고, Chan과 커크패트릭-자이델이 이를 달성하므로 평면 볼록 껍질은 이미 끝난 문제다. 남은 것은 상수와 강건성뿐인데, 그 “뿐”이 실무의 전부라는 게 함정.

5. 3차원과 그 위[편집]

3차원에서는 껍질이 다면체가 되고, 오일러 공식에 의해 꼭짓점 $h$ 개짜리 볼록다면체의 면·모서리 수도 $O(h)$ 다. 그래서 3D 껍질도 $O(n \log n)$ 이 가능하다 — 프레파라타-홍(1977)의 분할정복, 클라크슨-쇼어 계열의 무작위 증분법이 대표적이다.

$d \ge 4$ 부터는 사정이 달라진다. 상계 정리(McMullen)에 따라 $n$ 개 점의 $d$ 차원 껍질은 최대 $\Theta(n^{\lfloor d/2 \rfloor})$ 개의 면을 가질 수 있다. 즉 고차원에서는 출력 자체가 폭발하므로 “빠른 알고리즘”이라는 말이 무의미해진다. 고차원에서 껍질을 통째로 구하려는 시도는 대개 설계 실수이고, 필요한 것은 보통 지지함수 오라클이나 분리 초평면 하나뿐이다.

QuickHull(Barber, Dobkin, Huhdanpää 1996)은 임의 차원을 다루는 사실상의 표준 구현 qhull 의 알고리즘이다. 이름대로 퀵정렬을 닮았다 — 극단 점 몇 개로 초기 심플렉스를 만들고, 각 면 바깥에 남은 점 중 가장 먼 점을 골라 그 점에서 보이는 면들을 통째로 제거한 뒤 “지평선” 모서리에서 새 면을 세운다. 내부에 갇힌 점은 즉시 버려지므로 실전 성능이 좋지만, 최악의 경우와 퇴화 입력에서의 처리는 여전히 만만치 않다.³

5.1. 포물면 리프팅 — 들로네와의 관계[편집]

평면 점 $(x_i, y_i)$ 를 3차원 포물면 위로 들어올린다.

(x_i,\, y_i) \ \longmapsto\ \bigl(x_i,\ y_i,\ x_i^2 + y_i^2\bigr)

이렇게 올린 점들의 하부 볼록 껍질(아래에서 올려다볼 때 보이는 면들)을 평면으로 도로 사영하면, 그것이 정확히 원래 점들의 들로네 삼각분할이다. 이유도 직관적이다 — 평면의 원 $x^2+y^2+Dx+Ey+F=0$ 은 리프팅 후 평면 $z + Dx + Ey + F = 0$ 이 되므로, “원 안에 있다”가 “평면 아래에 있다”로 번역된다. 그래서 들로네의 인서클 판정은 리프팅된 네 점의 3D 방향 판정과 같은 계산이고, 반대로 상부 껍질은 최원점 들로네(furthest-point Delaunay)를 준다. 보로노이 다이어그램까지 한 걸음 더 가면, 각 점에 접평면을 세운 것들의 상포락이 보로노이 셀이 된다. 요컨대 껍질 코드 하나만 제대로 짜면 들로네·보로노이·메시 생성 전처리가 딸려 온다.

6. 수치 강건성 — 술어가 전부다[편집]

볼록 껍질 알고리즘의 본체는 사실상 방향 판정 술어 하나다.

\mathrm{orient2d}(a,b,c) = \operatorname{sign} \begin{vmatrix} b_x - a_x & b_y - a_y \\ c_x - a_x & c_y - a_y \end{vmatrix}

부호가 양이면 좌회전, 음이면 우회전, 0이면 공선. 문제는 이 행렬식을 부동소수점 연산으로 순진하게 계산하면 거의 공선인 세 점에서 부호가 틀린다는 것이다. 그리고 기하 알고리즘은 술어 결과들 사이의 논리적 일관성을 가정하고 짜여 있기 때문에, 한 번의 부호 오류가 “스택이 비었는데 pop”, “껍질이 자기 자신과 교차”, 심하면 무한 루프로 번진다. 케트너 등(2008)은 그레이엄 스캔이 평범해 보이는 입력에서 어떻게 어긋난 답을 내놓는지를 교과서적 반례로 정리했다.⁴

해법은 오차를 줄이는 게 아니라 부호를 정확히 맞히는 것이다.

정확 산술 — 좌표가 정수나 유리수면 다중정밀도로 행렬식을 그대로 계산한다. 느리지만 확실.
적응적 정밀도 — 슈척(Shewchuk, 1997)의 방식. 먼저 부동소수점으로 계산하고 오차 한계를 함께 추정해, 부호가 확실하면 즉시 반환하고 애매할 때만 정밀도를 단계적으로 올린다. 99% 이상의 호출이 첫 단계에서 끝나므로 사실상 공짜에 가깝다.
정확 기하 계산 패러다임 — 좌표는 근사해도 좋되 모든 분기 판정은 정확히. CGAL을 비롯한 라이브러리들이 이 원칙 위에 서 있다.

여기서 얻을 교훈은 일반적이다. 수치해석의 다른 분야에서는 “오차가 작으면 된다”가 통하지만, 계산기하에서는 오차가 아무리 작아도 부호가 틀리면 알고리즘의 조합적 전제가 무너진다. 잔차가 $10^{-16}$ 이라도 위상이 깨지면 답이 아니라 크래시가 나온다.

7. 응용[편집]

충돌 판정. GJK 알고리즘·분리축 정리 계열은 전부 볼록체를 요구한다. 그래서 아티스트가 만든 오목 메시는 볼록 껍질로 감싸거나 여러 볼록 조각으로 근사 분해(V-HACD 등)한 뒤 물리 엔진에 넘긴다. 경계 볼륨 계층의 k-DOP은 아예 “방향 $k$ 개로 자른 볼록 껍질”이다.
최적화의 볼록 완화. 정수 해집합 $S \subset \mathbb{Z}^n$ 위의 선형계획은 $\mathrm{conv}(S)$ 위의 선형계획과 최적값이 같다. 이 사실이 정수계획법의 이론적 출발점이고, 절단평면법은 “정수 껍질에 조금씩 다가가는 부등식을 추가하는” 작업이다. 문제는 그 껍질을 기술하는 부등식이 지수 개일 수 있다는 것이라, 실제로는 선형계획법 완화 + 분리 오라클로 우회한다(분지한정법 참고).
통계와 데이터. 볼록 껍질 벗기기(convex hull peeling)로 다변량 이상치를 걸러내거나, 베지어 곡선의 제어점 껍질로 곡선의 존재 범위를 보증하는 데 쓴다.
회전 캘리퍼스. 껍질을 얻고 나면 지름(가장 먼 두 점), 폭, 최소 넓이 둘러싸는 직사각형이 껍질을 한 바퀴 도는 $O(h)$ 스캔으로 떨어진다.

8. 관련 문서[편집]

균등분포 원판에서는 $O(n^{1/3})$ , 정규분포에서는 $O(\sqrt{\log n})$ 이다. 즉 100만 점을 뿌려도 껍질 꼭짓점은 수십 개 수준이라는 뜻이라, 자비 감싸기의 $O(nh)$ 가 이론적 최악에 비해 실전에서 억울할 만큼 잘 돈다. 물론 데이터가 원 위에 놓이는 순간 $h=n$ 이 되어 즉시 $O(n^2)$ 로 응징당한다. ↩
볼록 껍질과 정렬의 관계는 양방향이다. 정렬이 껍질로 환산되는 것(하한 증명)과 반대로, 이미 정렬된 점 집합의 껍질은 모노톤 체인으로 $O(n)$ 에 나온다. “정렬만 되어 있으면 기하가 쉬워진다”는 이 바닥의 오래된 국룰이 여기서도 성립. ↩
3D 껍질을 처음 구현하면 십중팔구 “동일 평면 위의 네 점”에서 무한 루프에 빠진다. 퇴화 입력(같은 점, 공선, 공면)을 어떻게 처리할지는 알고리즘 논문이 대체로 “구현 세부사항”이라며 넘기는 부분인데, 실제 코드에서는 그게 분량의 절반을 먹는다. 논문 5쪽, 코드 2000줄의 전형적 사례. ↩
Kettner, Mehlhorn, Pion, Schirra, Yap (2008), Classroom Examples of Robustness Problems in Geometric Computations. “설마 이런 걸로 깨지겠어”라는 마음가짐으로 짠 껍질 코드가 정확히 어떻게 깨지는지를 그림까지 붙여 보여 주는 논문이라, 계산기하를 처음 구현하는 사람에게 트라우마 겸 예방접종으로 추천된다. ↩