<aside> ✅

Convex hull은 주어진 점들을 전부 포함하면서도 가능한 한 작은 볼록 집합이에요.

분석에서는 이걸 이용해 “변수들의 가능한 상태 공간”을 간단한 볼록 다면체(polyhedron)로 표현하죠.

</aside>

Convex Hull (볼록 껍질)

• 정의 어떤 점 집합 $S \subseteq \mathbb{R}^n$이 있을 때, convex hull은 S를 포함하는 가장 작은 볼록 집합(convex set)입니다. 기호로는 보통 conv(S) 또는 **CH(S)**라고 씁니다.

• Convex set (볼록 집합) 집합 C가 convex 하다는 것은, 임의의 두 점 x, y \in C에 대해, 그 사이를 잇는 선분 전체가 C 안에 포함된다는 뜻입니다:

  $$ \forall \lambda \in [0,1],\; \lambda x + (1-\lambda)y \in C $$

• 즉, convex hull

  • S의 모든 점을 “고무줄”로 둘러싸듯 감싸는 최소한의 볼록 다각형/다면체.
  • 직관적으로는 점들을 포함하는 가장 작은 볼록 영역.

프로그램 분석과의 관계

• polyhedra abstract domain에서 상태를 나타낼 때, 점들의 집합이나 해 집합을 다루게 됨.
• 이 집합을 직접 쓰기엔 복잡하므로, 그 점들을 포함하는 convex hull로 근사.
• 따라서 convex hull = 점들의 아핀 부등식 시스템으로 표현 가능한 최소 볼록 근사라고 볼 수 있습니다.