TL;DR

  • 볼록 껍질의 면 평면을 병합하거나 제거한 뒤 쌍대다면체의 꼭짓점으로 바꾸어 볼록 껍질을 다시 구성하는 방식은 면 평면 클리핑을 반복하는 방식의 대안임.
  • 원점을 내부에 포함하는 볼록 다면체의 지지 함수는 꼭짓점별 방향 영역에서 선형이며, 그 준위집합은 중첩된 극쌍대다면체임.
  • 극쌍대다면체의 면은 원래 다면체의 꼭짓점에, 극쌍대다면체의 꼭짓점은 원래 다면체의 면에 대응함.
  • 원래 면 평면 n·x = d는 극쌍대다면체의 꼭짓점 n/d로 대응하고, 구면에 투영한 모서리는 가우스 사상을 이룸.
  • 면 법선들을 병합하거나 제거하는 작업은 극쌍대다면체의 꼭짓점을 편집하는 작업이며, 새 다면체의 면 w·y = 1은 단순화된 다면체의 꼭짓점 w를 정의함.

직관

  • 볼록 껍질을 단순화하는 일반적인 방법은 모든 면 평면을 구한 다음 일부를 병합하거나 제거하고, 남은 평면으로 껍질을 다시 구성하는 방식임.
  • 재구성 방법은 두 가지임.
  • 각 평면을 큰 사각형으로 만들고 나머지 모든 평면으로 잘라내는 과정을 평면마다 반복함.
  • 면 법선들의 볼록 껍질을 구함. 면 평면 n·x = d는 점 n/d가 되며, 이 점들의 볼록 껍질은 쌍대다면체의 볼록 껍질이고 그 면들이 단순화된 껍질의 꼭짓점을 제공함.
  • 원점을 내부에 포함하는 꼭짓점 v₁, v₂, …, vₖ의 볼록 다면체 P에 대해 지지 함수는 h(y) = maxₓ∈P(x·y) = maxᵢ(vᵢ·y)임.
  • 지지 함수는 조각별 선형 함수임. 각 선형 영역은 쐐기이며, 쐐기 i는 지지점이 vᵢ인 방향들의 집합임. 구면에서 이 쐐기들은 가우스 사상의 영역임.
  • h가 각 쐐기 안에서 선형이므로 준위집합은 쐐기 내부에서 평평하고, 쐐기 사이의 경계에서만 꺾임. 이에 따라 다음 대응 관계가 성립함.
  • 준위집합의 와이어프레임을 투영하면 가우스 사상이 됨.
  • 준위집합의 면은 가우스 사상의 각 영역 위에 놓이며, P의 꼭짓점마다 하나씩 대응함.
  • 준위집합의 꼭짓점은 호가 만나는 지점 위에 놓이며, P의 면마다 하나씩 대응함.
  • 그림의 예시는 정육면체 [-1,1]³, 한 옥탄트를 잘라낸 지지 함수 h(y) = |y₁| + |y₂| + |y₃|의 준위집합, 정육면체의 가우스 사상을 같은 각도에서 보여주는 구성임. 준위집합은 중첩된 팔면체이며 와이어프레임은 가우스 사상과 일치하고, 법선이 v인 팔면체 면은 강조된 v 영역 위에 놓임.

정리

  • P의 극쌍대는 P° = {y : 모든 x∈P에 대해 x·y ≤ 1}임.
  • c > 0일 때 준위집합 {h ≤ c}는 cP°이며, P°는 볼록 다면체임.
  • P°의 면은 P의 꼭짓점에 대응함. 면 i는 평면 vᵢ·y = 1에 놓이며 법선은 vᵢ임.
  • P°의 꼭짓점은 P의 면에 대응함. 평면 n·x = d인 P의 면은 꼭짓점 n/d가 되며, P°의 모서리를 구면에 투영하면 가우스 사상이 됨.

증명

  • 지지 함수의 정의에 따라 h(y) ≤ 1은 모든 x∈P에 대해 x·y ≤ 1이라는 조건과 동치이므로 {h ≤ 1} = P°임. h(ty) = t h(y), t > 0의 동차성에 따라 다른 준위집합은 이를 크기 조정한 집합이며, {h ≤ c} = cP°임.
  • h는 선형 함수들의 최댓값이므로 P° = ⋂ᵢ{y : vᵢ·y ≤ 1}이며, 유한 개의 반공간의 교집합임. 원점이 P 내부에 있으므로 유계이기도 함. 구체적으로 m = min_{||y||=1} h(y) > 0이고 h(y) ≥ m||y||임.
  • 쐐기 i에서 h(y) = vᵢ·y이므로 해당 쐐기 안에서 P°의 경계는 평면 vᵢ·y = 1임. 서로 다른 꼭짓점은 서로 다른 평면을 만들며, 이웃한 면들은 쐐기 경계를 따라 각을 이루며 만남.
  • 동차성에 따라 원점에서 뻗는 각 광선은 y/h(y) 지점에서 P°의 경계를 정확히 한 번 통과함. 따라서 구면 투영은 P°의 각 면을 해당 쐐기로, 각 모서리를 쐐기 경계로 보내며, 이것이 가우스 사상임.
  • P°의 꼭짓점은 세 개 이상의 쐐기가 만나는 곳에 있으며, P의 면 법선 n 방향에 놓임. 해당 광선에서 h(tn) = td = 1이므로 t = 1/d이고, 꼭짓점은 n/d임.
  • 원점이 P 내부에 있지 않다면 일부 방향에서 h ≤ 0이 될 수 있음. 그런 광선은 h = 1에 도달하지 않으며 준위집합은 유계가 아님.

껍질 단순화로 돌아가기

  • 면 법선을 병합하거나 제거하는 작업은 P°의 꼭짓점을 편집하는 작업이며, 편집한 점들의 볼록 껍질을 취하면 P°를 다시 구성함.
  • 정리의 대응 관계에 따라 새 껍질의 각 면 w·y = 1은 단순화된 다면체의 꼭짓점 w를 제공함.