볼록 껍질 알고리즘

볼록 껍질 알고리즘은 다양한 객체에 볼록 껍질을 만드는 알고리즘이다. 볼록 껍질 알고리즘은 수학 및 컴퓨터 과학에 광범위하게 적용되고 있다.

계산기하학에서, 유한한 점의 집합에 대해 볼록 껍질을 계산하는다양한 알고리즘들이 다양한 시간 복잡도로 제안되었다.

볼록 껍질을 계산하는 것은 모호하지 않으면서도 효율적으로 요구되는 볼록한 모양을 구성하는 것을 의미한다. 이러한 알고리즘의 복잡도는 주로 입력되는 점의 개수인 n 과, 간혹 볼록 껍질을 구성하는 점의 개수인 h 에 따라 비교된다.

평면의 경우

알고리즘에 입력되는 일반적인 경우는 데카르트 평면 위에서 순서가 주어지지 않은 점들의 유한한 점들의 집합이다. 중요하고도 특별한 경우로는 점들이 단순 다각형의 경계에서의 순서로 주어지는 경우가 있는데, 나중에 다른 분리된 부분에서 서술한다.

모든 점이 같은 직선 상에 있지 않은 경우, 볼록 껍질은 입력된 점들의 집합중 일부를 정점으로 하는 볼록 다각형이다. 볼록 다각형의 가장 일반적인 표현방법은 정점들을 가장자리를 시계방향 혹은 반시계방향순으로 정렬된 목록으로 표현하는 것이다. 몇몇 적용에서는 볼록 다각형을 반평면의 교집합으로 표현하는 것이 더 편리할 때도 있다.

계산 복잡도의 하계

평면상의 유한한 점들의 집합에 대해 볼록 껍질을 볼록 다각형으로 표현하는 것의 계산 복잡도의 하계는 다음의 환산을 이용하여 정렬하는 방법으로 쉽게 보여질 수 있다. 숫자로 이루어진 집합 $x_{1},\dots ,x_{n}$ $(x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})$. 이때, 이 점들은 볼록 함수인 포물선 위에 있으며, 볼록 껍질의 가장 자리를 따라가면 숫자들의 정렬된 순서 $x_{1},\dots ,x_{n}$ 분명히, 숫자들을 점들로 변환시키고 그들의 정렬된 순서로 추출하는데에는 선형 시간이 걸린다. 따라서 일반적으로 n개의 점들의 볼록껍질은 정렬보다 빠르게 계산될 수 없다.

Ω(n log n)이라는 기준은 비교만 가능하고 산술 연산이 수행될 수 없는 계산의 결정 트리 모델에서 정렬의 하계로 증명되었다. 그러나 이 모델에서 볼록 껍질은 계산될 수 없다. 정렬은 또한 계산의 대수적 결정 트리모델 에서도 Ω(n log n) 시간을 요구하며, 이 모델은 볼록 껍질에 조금 더 적합하다. 그러나 이 모델에서도 볼록 껍질은 Ω(n log n) 시간을 요구한다. 그러나 O(n log n)시간보다 빠르게 정렬(예를 들어, 정수 정렬 알고리즘)될 수 있는 산술 계산의 모델에서는, 평면 볼록 껍질은 조금 더 빠르게 계산될 수 있다. 예를 들어 볼록 껍질을 위한 그레이엄 스캔 알고리즘은 한번의 정렬 과정과 뒤따르는 선형의 추가 작업으로 구성된다.

최적의 출력-민감 알고리즘

위에서 언급했듯이, 볼록 껍질을 찾는 입력 크기 n의 함수의 시간 복잡도는 Ω(n log n)의 하계를 갖는다. 그러나 몇몇 볼록 껍질 알고리즘의 시간 복잡도는 입력 크기 n 과 출력 크기 h (껍질속의 점의 개수)모두를 갖는 특성이 있다. 이러한 알고리즘을 출력-민감한 알고리즘이라고 부른다. 이것들은 h = o(n)인 경우 Θ(n log n) 알고리즘보다 점근적으로 더 효율적일 수 있다.

최악의 상황에서 실행 시간이 출력-민감한 볼록껍질 알고리즘의 하계는 평면의 경우 Ω(n log h)임이 입증되었다. 이러한 최적의 시간 복잡도를 달성하는 몇몇 알고리즘들이 있다. 출력-민감 알고리즘은 1986년에 데이비드 커크패트릭과 레이먼드 자이델에 의해 소개되었다.( 그들은 그 알고리즘을 "궁극적인 볼록 껍질 알고리즘"으로 불렀다.) 더 많이 간단한 알고리즘은 1966년 티모티 찬에 의해 개발된 찬의 알고리즘이다.

알고리즘

널리 알려진 볼록껍질 알고리즘은 처음 출판된 날짜 순서대로 아래에 목록으로 정리되어있다.각 알고리즘의 시간 복잡도는 입력되는 점의 개수인 n 과 볼록 껍질을 구성하는 점의 개수인 h에 따라 말해진다. 최악의 경우, h는 n만큼 커질 수 있음에 유의해야한다.

• 자비스의 행진으로 알려진 선물 포장 알고리즘 — O(nh)
  가장 간단한 평면 알고리즘중 하나이다. 그러나 최악의 경우에 가장 효율적인 알고리즘은 아니다. 이 알고리즘은 1970년에 찬드와 카퍼, 그리고 1973년 R. A. 자비스에 의해 독립적으로 만들어졌다. 이 알고리즘은 점의 개수를 n이라고 하고, 껍질을 이루는 점의 개수를 h라고 할 때, O(nh)의 알고리즘 분석을 가진다. 최악의 경우에 시간 복잡도는 Θ(n²)이다.
• 그레이엄 스캔 — O(n log n)
  1972년 로널드 그레이엄에 의해 출판된 조금 더 정교하지만 훨씬 더 많이 효율적인 알고리즘이다. 만약 점들이 이미 고정벡터에 대한 각도나 좌표순으로 정렬된 경우 이 알고리즘은 O(n)시간에 수행된다.
• 퀵 헐 
  1977년 W.Eddy와 1978년 A.Bykat에 의해 독립적으로 만들어졌다. 퀵 정렬 알고리즘 같은 방법으로, 이 알고리즘은 O(n log n)의 시간 복잡도가 예상되지만, 최악의 경우 O(n²)까지 악화될 수 있다.
• 분할 정복 — O(n log n)
  1977년 프레파라타와 홍에 의해 출판된 또다른 O(n log n) 알고리즘이다. 이 알고리즘은 또한 삼차원의 경우에도 적용이 된다.
• 앤드류의 알고리즘으로 알려진 모노톤 체인 — O(n log n)
  A.M. 앤드류에 의해 1979년에 출판되었다. 이 알고리즘은 점들을 좌표에 따라 사전순으로 정렬한 그레이엄 스캔의 변형으로 볼 수 있다. 입력이 이미 정렬되어 있는 경우, 이 알고리즘은 O(n)시간이 걸린다.
• 점진적 볼록껍질 알고리즘 — O(n log n)
  1984년에 마이클 캘레이에 의해 출판되었다.
• 궁극의 평면 볼록 껍질 알고리즘 — O(n log h)
  처음으로 최적화된 출력-민감한 알고리즘으로, 정복 전에 결혼이라는 기술을 사용하였다. 데이비드 커크패트릭과 레이먼드 자이델에 의해 1986년에 출판되었다..
• 찬의 알고리즘 — O(n log h)
  1996년 찬에 의해 만들어진 조금 더 간단한 최적화된 출력-민감지 알고리즘.

Akl–Toussaint 휴리스틱

아래의 간단한 휴리스틱은 성능을 향상시키기 위해서 볼록 껍질 알고리즘 구현의 첫 단계로 사용된다. 이것은 Selim Akl과 G. T. Toussaint이 1978년에 제시한 효율적인 볼록 껍질 알고리즘에 기반한다. 이 아이디어는 어떤 방식으로도 볼록 껍질의 부분이 될 수 없는 많은 점들을 빠르게 배제하는 것이다. 이 방법은 다음의 아이디어를 기반으로 한다.  x좌표가 가장 높은 점과 가장 낮은 점을 찾고, y좌표가 가장 높은점과 낮은 점을 찾는다(각 연산은 O(n)에 수행된다.). 이 네 점들은 볼록 사각형을 이루고, 이 사변형에 포함되는 모든 점들(처음에 고른 네 정점은 제외한다.)은 볼록 껍질의 부분이 될 수 없다. 이 사변형 안의 모든 점을 찾는것은 O(n)이므로, 전체 작업은 O(n)이다. 추가적으로, x좌표와 y좌표의 합이 제일 큰 점과 제일 작은 점,  x좌표와 y좌표의 차이가 제일 큰 점과 제일 작은 점 또한 사변형에 추가되어서 내부의 점들을 안전하게 무시할 수 있는 불규칙한 볼록 팔각형을 이루게 할 수도 있다. 점들이 무작위적인 경우, 좁게 모여있을 수도 있지만 일반적으로는 확률 질량 함수의 범주에 포함될 것이다. 이 거쳐가는 선처리 과정은 볼록 껍질 알고리즘을 선형 예상 시간에 작동하게 한다.

On-line and dynamic convex hull problems

위의 설명에서는 모든 입력 점들을 한번에 알게 된 경우만 고려한다. 여기에 다른 두가지 설정도 고려해 볼 수 있다.

• 온라인 볼록껍질 문제: 입력되는 점들은 한번에 하나씩 순차적으로 얻을 수 있다. 각 점이 입력으로 도착했을 때, 지금까지 얻은 점집합에 대해 볼록껍질은 반드시 효율적으로 계산되어야 한다.
• 동적 볼록 껍질 보수: 입력되는 점들이 순차적으로 삽입되거나 제거되고, 볼록 껍질이 모든 삽입/제거 연산 이후에 갱신되어야 한다.

점의 삽입은 볼록 껍질의 정점들의 개수를 최대 1개까지 늘릴 수 있고, 삭제는 n-꼭짓점 볼록 껍질을 n-1-꼭짓점 볼록껍질으로 변화시킬 수 있다.

점근적으로 최적일 때, 온라인 버전은 점당 O(log n)으로 처리될 수 있다. 동적인 버전은 한번의 연산당 O(log² n)으로 처리될 수 있다.

단순 다각형

맥 칼럼과 아비스는 O(n)시간에 단순다각형 v_1, ..., v_n의 볼록 껍질을 구성하는 옳은 알고리즘을 고안하였다. 기본적인 생각은 매우 쉽다. 가장 왼쪽에 있는 정점은 볼록 껍질 위에 있고, 그것을 h_1이라고 하자.  두번째 점은 볼록 껍질을 이룰 후보 정점으로 간주된다.  At 각 단계에서는 다각형에서 연속된 세 정점을 보는데, 처음 두개는 자라나고 있는 볼록 껍질에 잠정적으로 포함된 것으로 보고 세번째 정점은 처리되지 않은 다각형의 정점으로 본다. 이 점들을 $h_{k-1},h_{k},v_{i}$. 만약 세 점이 이루는 각이 볼록하다면 $h_{k+1}=v_{i}$ 만약 각이 오목하다면 중간 점($h_{k}$)은 제거되고 $h_{k-2},h_{k-1},v_{i}$ $h_{1}$. 그 뒤 다각형을 따라 다음 정점이 테스트될 세 정점에 추가되고, 과정이 반복된다.  그러나 이전에 출판된 몇개의 논문들은 다각형으로부터 정점을 제거하였을 때 자기 교차 다각형이 발생할 가능성을 간과하였고, 알고리즘이 유효하지 않은 결과를 나타내었다. 다행히도, 이 경우는 효율적으로 처리될 수 있다.  나중에 Tor와 Middleditch (1984년, "단순 다각형의 볼록 분해(Convex Decomposition of Simple Polygons)") 그리고 독립적으로 Melkman (1985년, "단순 다변형의 볼록 껍질로의 온라인 구성(Online Construction of the convex hull of a simple polyline)")은 같은 시간 복잡도를 갖는 더 간단한 접근법을 발견하였다.

더 높은 차원

삼차원의 경우 알려진 몇가지 알고리즘은 임의의 차원에서도 사용될 수 있다.

유한한 점들의 집합에 대해서, 볼록 껍질은 3차원에서는 볼록 다면체(convex polyhedron)이고, 일반적으로는 어떠한 숫자의 차원에서 입력된 점의 일부를 정점으로 하는 볼록 다포체(convex polytope)이다. 그러나 그것의 표현은 평면의 경우만큼 간단하지 않다. 높은 차원에서, 심지어 볼록 다포체의 정점들이 알려져 있더라도 볼록 다포체의 면들을 구성하는 것은 사소한 일이 아니고, 주어진 면으로부터 점들을 구성하는 것은 또 다른 문제이다. 출력되는 면들의 정보의 크기는 입력되는 정점들의 크기에 비해 지수적으로 클 것이고, 입력과 출력 둘다 유사한 크기에 있을지라도 알려진 높은 차원에서의 볼록 껍질 알고리즘은 퇴화된 입력들과 높은 복잡도의 중간 결과들 모두 문제가 되기 때문에 출력-민감하지 않다.

같이 보기

• 직교 볼록 껍질

참고 문헌

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 33.3: Finding the convex hull, pp. 947–957.
• Franco P. Preparata, S.J. Hong. Convex Hulls of Finite Sets of Points in Two and Three Dimensions, Commun. ACM, vol. 20, no. 2, pp. 87–93, 1977.
• Mark de Berg; Marc van Kreveld; Mark Overmars; Otfried Schwarzkopf (2000). 《Computational Geometry》 2 revis판. Springer-Verlag. ISBN 3-540-65620-0.  Section 1.1: An Example: Convex Hulls (describes classical algorithms for 2-dimensional convex hulls). Chapter 11: Convex Hulls: pp. 235–250 (describes a randomized algorithm for 3-dimensional convex hulls due to Clarkson and Shor).

외부 링크

• Weisstein, Eric Wolfgang. “Convex Hull”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• 전산기하학 알고리즘 라이브러리 CGAL을 기반으로 한 2차원, 3차원, d 차원 볼록 껍질
• 볼록껍질, 들로네 삼각형, 보로노이 다이어그램, 반공간 교집합을 위한 Qhull 코드
• 자비스의 행진, 그레이엄 스캔, 퀵 (분할정복) 알고리즘, 찬 알고리즘의  플래시 swf로 제작된 예시
• C#으로 제작된 선물 포장 알고리즘