볼록 껍질 알고리즘은 주어진 점들의 집합을 포함하는 가장 작은 볼록 다각형 또는 다면체를 찾는 알고리즘을 의미한다. 평면 상의 점 집합에 대한 볼록 껍질은 정렬 문제와 관련되어 있으며, 계산 복잡도는 입력 점의 개수와 출력 점의 개수에 따라 달라진다. 대표적인 알고리즘으로는 그레이엄 스캔, 퀵헐, 자비스 행진, 찬의 알고리즘 등이 있다. 온라인 및 동적 볼록 껍질 문제, 단순 다각형의 볼록 껍질 구성 문제도 존재하며, 3차원 이상의 공간에서는 볼록 다면체 또는 다포체를 구성하는 문제로 확장된다.
더 읽어볼만한 페이지
볼록 껍질 알고리즘 - 그레이엄 스캔 그레이엄 스캔은 점들의 집합에서 볼록 껍질을 찾는 알고리즘으로, y좌표가 가장 작은 점을 기준으로 각도 순으로 정렬한 후 스택을 사용하여 볼록 껍질을 구성하며, 이미지 처리 등 다양한 분야에 활용되고 시간 복잡도는 O(n log n)이다.
볼록 껍질 알고리즘 - 선물 포장 알고리즘 자비스 행진 알고리즘은 볼록 껍질을 찾는 알고리즘으로, 가장 왼쪽 점부터 시작하여 가장 왼쪽으로 꺾이는 점을 선택하는 '선물 포장' 방식으로 볼록 껍질을 구성하며, 시간 복잡도는 O(nh)이다.
최단 거리 문제 최대 거리 문제 최소 외접원 문제 선형 계획법 기하학적 최적화 회전하는 캘리퍼스 삼각 분할 복셀 계산 기하학 주제 목록
2. 평면의 경우
알고리즘에 입력되는 일반적인 경우는 직교 좌표계 위의 유한한 점들의 집합이며, 이 점들의 순서는 주어지지 않는다.
모든 점이 같은 직선 위에 있지 않다면, 이 점들의 볼록 껍질은 입력된 점들 중 일부를 꼭짓점으로 하는 볼록 다각형이다. 볼록 껍질을 표현하는 가장 일반적인 방법은 꼭짓점들을 경계를 따라 시계 방향 또는 반시계 방향 순서로 정렬된 목록으로 나타내는 것이다. 일부 응용 프로그램에서는 볼록 다각형을 여러 반평면들의 교집합으로 표현하는 것이 더 편리할 수도 있다.
점들이 단순 다각형의 경계 순서대로 주어지는 특수한 경우는 별도로 다룬다.
2. 1. 계산 복잡도의 하계
평면상에 주어진 유한한 점들의 집합에 대해, 그 볼록 껍질을 볼록 다각형으로 표현하는 문제의 계산 복잡도 하계는 정렬 문제로의 환원을 통해 쉽게 이해할 수 있다. 예를 들어, 정렬하고자 하는 ''n''개의 숫자 가 주어졌을 때, 이들을 평면 위의 점 으로 변환할 수 있다. 이 점들은 볼록 함수인 포물선 위에 놓이게 된다. 이 점들의 볼록 껍질을 구하고 그 경계를 따라 정점들을 순회하면, 원래 숫자들의 정렬된 순서 를 얻을 수 있다. 숫자를 점으로 변환하고, 볼록 껍질에서 정렬된 순서를 추출하는 과정은 선형 시간 안에 완료될 수 있다. 따라서 일반적으로 ''n''개의 점에 대한 볼록 껍질 계산은 정렬보다 빠르게 수행될 수 없다.
정렬 문제의 계산 복잡도 하계는 Ω(''n'' log ''n'')으로 알려져 있다. 이는 비교 연산만 가능하고 산술 연산은 불가능한 결정 트리 모델에서 증명되었지만, 이 모델로는 볼록 껍질 자체를 계산할 수 없다. 볼록 껍질 계산에 더 적합한 모델인 대수적 결정 트리 모델에서도 정렬 문제는 Ω(''n'' log ''n'')의 시간을 필요로 하며, 볼록 껍질 계산 역시 동일하게 Ω(''n'' log ''n'')의 시간이 필요하다.[23][1][11]
그러나 특정 계산 모델, 예를 들어 컴퓨터 산술 모델에서는 정수 정렬 알고리즘 등을 사용하여 숫자를 ''O''(''n'' log ''n'') 시간보다 빠르게 정렬하는 것이 가능하다. 이러한 모델에서는 평면 볼록 껍질 역시 더 빠르게 계산될 수 있다. 예를 들어, 볼록 껍질을 구하는 그레이엄 스캔 알고리즘은 한 번의 정렬 단계와 그 이후의 선형 시간 복잡도를 가지는 추가 작업으로 구성된다.
2. 2. 최적의 출력-민감 알고리즘
입력 점의 개수 ''n''뿐만 아니라 결과로 나오는 볼록 껍질을 구성하는 점의 개수 ''h''에도 시간 복잡도가 의존하는 알고리즘을 출력-민감한 알고리즘이라고 부른다. 만약 볼록 껍질을 이루는 점의 개수 ''h''가 전체 점의 개수 ''n''에 비해 매우 작다면(''h'' = ''o''(''n'')), 이러한 출력-민감 알고리즘은 일반적인 Θ(''n'' log ''n'') 알고리즘보다 점근적으로 더 효율적일 수 있다.
평면에서 출력-민감 볼록 껍질 알고리즘의 최악 시간 복잡도 하계는 Ω(''n'' log ''h'')로 알려져 있다.[1] 이 최적의 시간 복잡도를 달성하는 여러 알고리즘이 존재한다. 이러한 최적 시간 복잡도를 만족하는 최초의 알고리즘은 1986년 커크패트릭과 자이델에 의해 발표되었으며, 그들은 이 알고리즘을 "궁극적인 볼록 껍질 알고리즘"이라고 명명했다. 이후 1996년에는 찬이 더 간단한 구조의 최적 알고리즘인 찬의 알고리즘을 개발했다.
2. 3. 알고리즘
알고리즘에 입력되는 일반적인 경우는 데카르트 평면 위에서 순서가 주어지지 않은 유한한 점들의 집합이다. 모든 점이 같은 직선 위에 있지 않다면, 볼록 껍질은 입력된 점들 중 일부를 꼭짓점으로 하는 볼록 다각형이다. 볼록 다각형을 표현하는 가장 일반적인 방법은 꼭짓점들을 경계를 따라 시계방향 또는 반시계방향 순서로 정렬된 목록으로 나타내는 것이다. 경우에 따라 볼록 다각형을 여러 반평면의 교집합으로 표현하는 것이 더 편리할 수도 있다.
평면 위의 유한한 점 집합이 주어졌을 때, 볼록 껍질을 볼록 다각형으로 찾는 문제의 계산 복잡도는 정렬 문제와 밀접하게 연관되어 있다. 예를 들어, 정렬해야 할 숫자 집합 ''x''1, ..., ''x''''n''이 있을 때, 이들을 평면 위의 점 (''x''1, ''x''12), ..., (''x''''n'', ''x''''n''2)으로 변환할 수 있다. 이 점들은 볼록 함수인 포물선 위에 놓이게 되므로, 이 점들의 볼록 껍질 꼭짓점을 순서대로 따라가면 원래 숫자들의 정렬된 순서를 얻을 수 있다. 숫자들을 점으로 변환하고, 볼록 껍질에서 정렬된 순서를 추출하는 과정은 선형 시간에 가능하다. 따라서 일반적인 경우, ''n''개의 점에 대한 볼록 껍질 계산은 정렬보다 빠르게 수행될 수 없다.
정렬 문제의 시간 복잡도 하한은 결정 트리 모델이나 대수 결정 트리 모델과 같은 계산 모델에서 Ω(''n'' log ''n'')으로 알려져 있으며, 이 하한은 볼록 껍질 계산 문제에도 동일하게 적용된다.[1][11] 즉, 입력 점의 개수가 ''n''일 때, 볼록 껍질을 찾는 알고리즘의 시간 복잡도는 최소 Ω(''n'' log ''n'')이다.
하지만 일부 볼록 껍질 알고리즘의 시간 복잡도는 입력 점의 개수 ''n''뿐만 아니라, 결과로 나오는 볼록 껍질을 구성하는 꼭짓점의 개수 ''h''에도 의존한다. 이러한 알고리즘을 출력-민감한 알고리즘이라고 부른다. 만약 ''h''가 ''n''에 비해 매우 작다면(''h'' = ''o''(''n'')), 출력 민감 알고리즘은 Θ(''n'' log ''n'') 복잡도를 가지는 알고리즘보다 점근적으로 더 효율적일 수 있다. 평면에서의 출력 민감 볼록 껍질 알고리즘의 최악 시간 복잡도 하한은 Ω(''n'' log ''h'')로 증명되었다.[1][12] 이 최적의 시간 복잡도를 달성하는 알고리즘들이 존재한다.
널리 알려진 볼록 껍질 알고리즘들은 다음과 같으며, 발표된 순서대로 나열하였다. 각 알고리즘의 시간 복잡도는 입력 점의 개수 ''n''과 볼록 껍질 위의 점 개수 ''h''를 기준으로 표기한다. 최악의 경우 ''h''는 ''n''과 같을 수 있음에 유의해야 한다.
'''자비스 행진 (선물 포장 알고리즘)''' — ''O''(''nh'') 가장 간단한 평면 알고리즘 중 하나이지만, 최악의 경우 시간 효율성이 가장 높지는 않다. 1970년 Chand와 Kapur, 1973년 R. A. 자비스에 의해 독립적으로 개발되었다. O(nh)의 시간 복잡도를 가지며, 최악의 경우 복잡도는 Θ(n2)이다.
'''그레이엄 스캔''' — ''O''(''n'' log ''n'') 그레이엄 스캔으로 2차원 볼록 껍질을 찾는 과정 1972년 로널드 그레이엄이 발표한 알고리즘으로, 조금 더 정교하지만 훨씬 효율적이다. 만약 점들이 특정 좌표나 고정된 벡터에 대한 각도 순서로 이미 정렬되어 있다면, O(''n'') 시간에 수행될 수 있다.
'''퀵 헐''' — ''O''(''n'' log ''n'') (평균), ''O''(''n''2) (최악) 1977년 W. Eddy와 1978년 A. Bykat에 의해 독립적으로 개발되었다. 퀵 정렬과 유사한 방식으로 작동하며, 평균적으로 ''O''(''n'' log ''n'')의 시간 복잡도를 가지지만, 최악의 경우 ''O''(''n''2)까지 성능이 저하될 수 있다.
'''분할 정복''' (병합 껍질) — ''O''(''n'' log ''n'') 1977년 프랑코 P. 프레파라타와 홍이 발표한 또 다른 ''O''(''n'' log ''n'') 알고리즘이다. 이 알고리즘은 3차원 공간에서도 적용 가능하다.[2]
'''모노톤 체인''' (앤드류 알고리즘) — ''O''(''n'' log ''n'') 1979년 A. M. 앤드류가 발표했다. 점들을 좌표 기준으로 사전순으로 정렬한 뒤 처리하는 방식으로, 그레이엄 스캔의 변형으로 볼 수 있다. 입력 점들이 이미 정렬되어 있다면 ''O''(''n'') 시간에 완료된다.
'''점진적 볼록 껍질 알고리즘''' — ''O''(''n'' log ''n'') 1984년 마이클 캘레이(Michael Kallay)가 발표했다.
'''커크패트릭-자이델 알고리즘''' (궁극의 평면 볼록 껍질 알고리즘) — ''O''(''n'' log ''h'') 최초의 최적 출력-민감한 알고리즘이다. '정복 전 결혼(marriage-before-conquest)'이라는 기법과 저차원 선형 계획법을 사용하여 분할 정복 알고리즘을 개선했다. 1986년 데이비드 G. 커크패트릭과 라이문트 자이델이 발표했다.
'''찬의 알고리즘''' — ''O''(''n'' log ''h'') 1996년 티모시 M. 찬이 개발한 더 간단한 최적 출력-민감한 알고리즘이다. 선물 포장 알고리즘과 작은 부분집합에 대한 ''O''(''n'' log ''n'') 알고리즘(예: 그레이엄 스캔) 실행을 결합하는 방식으로 작동한다.
2. 4. Akl–Toussaint 휴리스틱
Akl–Toussaint 휴리스틱은 볼록 껍질 알고리즘의 성능 향상을 위해 구현 초기에 적용하는 간단한 휴리스틱 기법이다. 1978년 셀림 아클(Selim Akl)과 G. T. 투생(G. T. Toussaint)이 제시한 효율적인 볼록 껍질 알고리즘을 기반으로 하며, 최종 볼록 껍질에 포함되지 않을 점들을 미리 빠르게 제거하는 것을 목표로 한다.
이 방법은 먼저 주어진 점들 중에서 x좌표가 가장 작은 점과 가장 큰 점, 그리고 y좌표가 가장 작은 점과 가장 큰 점을 찾는다. 이 네 점을 찾는 데는 각각 O(''n'')의 시간이 걸린다. 이 네 점은 하나의 볼록 사변형을 형성하게 되는데, 이 사각형 내부에 있는 점들(네 꼭짓점 제외)은 최종 볼록 껍질에 포함될 수 없으므로 계산에서 제외할 수 있다. 사각형 내부의 점들을 찾아 제거하는 과정 역시 O(''n'') 시간이 걸리므로, 이 전처리 단계 전체는 O(''n'') 시간에 완료된다.
선택적으로, 더 많은 점을 제거하기 위해 팔각형을 활용할 수도 있다. 앞서 찾은 네 점에 더해, x좌표와 y좌표의 합(x+y)이 가장 작은 점과 가장 큰 점, 그리고 x좌표와 y좌표의 차(x-y)가 가장 작은 점과 가장 큰 점을 추가로 찾는다. 이 여덟 개의 점은 불규칙한 볼록 팔각형을 형성하며, 이 팔각형 내부에 있는 점들 역시 안전하게 제거할 수 있다.
점들의 분포가 무작위적이거나 특정 확률 분포를 따르는 경우, 이 Akl–Toussaint 휴리스틱 전처리 단계를 통해 전체 볼록 껍질 알고리즘이 선형 기대 시간(O(''n''))에 실행되도록 도울 수 있다. 이는 알고리즘 자체의 최악 시간 복잡도가 더 높더라도(예: ''n''의 제곱) 평균적인 성능을 크게 향상시키는 효과를 가진다.[13]
3. 온라인 및 동적 볼록 껍질 문제
지금까지의 설명은 모든 입력 점을 미리 알고 있는 경우를 다루었다. 하지만 다른 두 가지 상황도 고려해 볼 수 있다.[1][14]
'''온라인 볼록 껍질 문제''': 입력 점들이 한 번에 하나씩 순차적으로 주어진다. 각 점이 입력될 때마다, 그때까지 주어진 점들의 집합에 대한 볼록 껍질을 효율적으로 계산해야 한다.
'''동적 볼록 껍질 유지''': 입력 점들이 순차적으로 삽입되거나 삭제될 수 있으며, 각 삽입 또는 삭제 연산 이후에 볼록 껍질을 갱신해야 한다.
점을 삽입하면 볼록 껍질의 꼭짓점(정점) 수가 최대 1개 늘어날 수 있다. 반면, 점을 삭제하면 ''n''개의 꼭짓점을 가진 볼록 껍질이 ''n-1''개의 꼭짓점을 가진 볼록 껍질로 바뀔 수 있다.
온라인 볼록 껍질 문제는 점 하나당 O(log ''n'')의 시간 복잡도로 처리할 수 있으며, 이는 점근적으로 최적이다. 동적 볼록 껍질 문제는 연산 한 번당 O(log2 ''n'')의 시간 복잡도로 처리할 수 있다.[1][15][23]
4. 단순 다각형
단순 다각형(자기 교차를 갖지 않는 다각형)의 볼록 껍질은 다각형 자체와, 다각형 경계의 일부 및 볼록 껍질의 한 변으로 둘러싸인 여러 개의 "포켓(pocket)"으로 구성된다.[4][16] 단순 다각형의 볼록 껍질을 구성하는 문제에 대해 많은 알고리즘이 발표되었지만, 그중 일부는 부정확하다는 지적이 있었다.[4][16]
단순 다각형(파랑)에 대한 볼록 껍질. 4개의 포켓(노랑)을 갖는다. 파랑과 노랑을 합한 영역이 볼록 껍질이다.
맥컬럼(McCallum)과 아비스(Avis)는 O(n) 시간 복잡도를 갖는 최초의 올바른 알고리즘을 고안했다.[5][17] 이 알고리즘은 가장 왼쪽에 있는 정점(h1)을 시작점으로 삼아 볼록 껍질을 점진적으로 구성한다. 각 단계에서는 현재까지 구성된 볼록 껍질의 마지막 두 정점(hk-1, hk)과 아직 처리되지 않은 다각형의 다음 정점(vi)을 고려한다. 세 점 hk-1, hk, vi가 이루는 각도가 볼록하면(즉, 좌회전 또는 직선), 다음 정점 vi를 껍질에 추가한다(hk+1 = vi). 만약 각도가 오목하면(우회전), 중간 정점 hk는 껍질 후보에서 제외하고, 그 이전의 두 정점(hk-2, hk-1)과 다음 정점 vi를 다시 검사하는 과정을 볼록한 각도가 나올 때까지 반복한다. 이 과정을 다각형의 모든 정점을 따라 진행한다. 초기 연구에서는 정점을 제거할 때 자기 교차 다각형이 발생할 가능성을 간과하여 알고리즘 오류가 발생하기도 했으나, 이후 이 문제는 효율적으로 처리되었다. 나중에 토르(Tor)와 미들디치(Middleditch) (1984년), 그리고 독립적으로 멜크만(Melkman) (1985년)은 같은 시간 복잡도를 가지면서도 더 간단한 접근법을 발견했다.
1983년 그레이엄(Graham)과 야오(Yao), 그리고 리(Lee)가 각각 제시한 더 단순화된 알고리즘들은 단 하나의 스택 자료 구조만을 사용한다.[6][7][18][19] 이 알고리즘들은 다각형의 가장 왼쪽 정점에서 시작하여 시계 방향으로 순회한다. 순회하면서, 아직 포켓 내부에 있는 것으로 확인되지 않은 정점들을 볼록한 순서대로 스택에 저장한다. 각 단계에서 알고리즘은 스택의 가장 위에 있는 정점에서 시작하여, 그 정점과 인접한 두 포켓 중 어느 쪽에도 속하지 않는 다음 정점까지 다각형 경로를 따라간다. 만약 스택의 맨 위 두 정점과 새로 고려되는 정점이 볼록한 형태를 이루지 않으면(오목하면), 스택에서 정점을 제거(pop)한 후에 새로운 정점을 스택에 추가(push)한다. 이 과정을 시계 방향 순회가 시작점으로 돌아올 때까지 반복하면, 최종적으로 스택에 남아있는 정점들의 시퀀스가 볼록 껍질이 된다.[6][7][18][19]
5. 더 높은 차원
유한한 점들의 집합에 대해, 볼록 껍질은 3차원에서는 볼록 다면체이고, 더 높은 임의의 차원에서는 입력된 점의 일부를 꼭짓점으로 하는 볼록 다포체이다.[24] 그러나 고차원에서의 볼록 껍질 표현은 평면의 경우처럼 간단하지 않다. 볼록 다포체의 꼭짓점들이 주어져도, 그 면들을 구성하는 것은 쉽지 않으며, 반대로 면들로부터 꼭짓점을 구성하는 것 역시 어려운 문제이다. 또한, 출력해야 하는 면 정보의 크기는 입력된 꼭짓점의 수에 비해 지수적으로 커질 수 있다.[25][10][22]
이러한 복잡성 때문에, 입력과 출력의 크기가 비슷하더라도 현재 알려진 고차원 볼록 껍질 알고리즘들은 출력 민감형 알고리즘이 아니다. 이는 알고리즘이 처리해야 하는 입력 데이터가 퇴화된 형태를 가지거나, 계산 과정에서 매우 복잡한 중간 결과들이 발생하는 문제 때문이다.[25][10][22]
3차원 및 임의의 차원에서 볼록 껍질을 계산하기 위한 여러 알고리즘이 알려져 있다.[8][20] 예를 들어, 찬의 알고리즘은 2차원과 3차원에서 사용될 수 있으며, 퀵헐(Quickhull) 알고리즘은 더 높은 차원의 볼록 껍질을 계산하는 데 사용된다.[9][21]
참조
[1]
서적
Computational Geometry
[2]
웹사이트
A Minimalist's Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm
https://tmc.web.engr[...]
2024-10-04
[3]
논문
A note on linear expected time algorithms for finding convex hulls
[4]
웹사이트
A History of Linear-time Convex Hull Algorithms for Simple Polygons
http://cgm.cs.mcgill[...]
2020-10-11
[5]
간행물
A linear algorithm for finding the convex hull of a simple polygon
[6]
간행물
Finding the convex hull of a simple polygon
[7]
간행물
On finding the convex hull of a simple polygon
[8]
문서
David Mount's Lecture Notes
http://www.cs.umd.ed[...] [9]
학술지
The quickhull algorithm for convex hulls
http://www.cise.ufl.[...]
1996-12-01
[10]
간행물
How good are convex hull algorithms?
[11]
서적
Computational Geometry
[12]
서적
Computational Geometry
[13]
논문
A note on linear expected time algorithms for finding convex hulls
[14]
서적
Computational Geometry
[15]
서적
Computational Geometry
[16]
웹사이트
A History of Linear-time Convex Hull Algorithms for Simple Polygons
http://cgm.cs.mcgill[...]
2020-10-11
[17]
간행물
A linear algorithm for finding the convex hull of a simple polygon
[18]
간행물
Finding the convex hull of a simple polygon
[19]
간행물
On finding the convex hull of a simple polygon
[20]
문서
David Mount's Lecture Notes
http://www.cs.umd.ed[...] [21]
학술지
The quickhull algorithm for convex hulls
1996-12-01
[22]
간행물
How good are convex hull algorithms?
[23]
서적
Computational Geometry
[24]
문서
찬의 알고리즘
[25]
인용
How good are convex hull algorithms?
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
