선물 포장 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
선물 포장 알고리즘은 주어진 점들의 집합에서 볼록 껍질을 찾는 알고리즘이다. 2차원 평면에서의 구현은 자비스 행진으로 알려져 있으며, 점의 개수 n과 볼록 껍질을 이루는 점의 개수 h에 대해 O(nh)의 시간 복잡도를 가진다. 이 알고리즘은 n이 작거나 h가 n에 비해 매우 작을 때 다른 볼록 껍질 알고리즘보다 좋은 성능을 보이며, 출력 민감 알고리즘으로 껍질 꼭지점의 수 h가 log n보다 작을 때 그레이엄 스캔보다 빠르다. 고차원으로 확장될 수 있으며, 찬의 알고리즘은 선물 포장 알고리즘과 그레이엄 스캔을 결합하여 O(n log h)의 시간 복잡도를 달성한다.
더 읽어볼만한 페이지
| 선물 포장 알고리즘 | |
|---|---|
| 알고리즘 개요 | |
| 종류 | 볼록 껍질 알고리즘 |
| 고안자 | 라비드 |
| 발견 시기 | 1970년 |
| 다른 이름 | 선물 포장(Gift wrapping), 자비스 행진(Jarvis march) |
| 성능 | |
| 최악의 경우 시간 복잡도 | O(nh) (n = 점의 수, h = 껍질의 점의 수) |
| 최적의 경우 시간 복잡도 | O(n) |
| 특징 | |
| 장점 | 간단하고 구현이 용이함 |
| 단점 | 2차원 평면에서만 작동 점의 수가 많을 때 비효율적 |
| 작동 방식 | |
| 시작점 | 가장 왼쪽 점 |
| 다음 점 찾기 | 가장 작은 각도를 가지는 점 |
| 종료 조건 | 시작점으로 돌아올 때 |
2. 평면에서의 적용
2차원의 경우, 이 알고리즘은 R. A. 자비스가 1973년에 출판한 이후 '''자비스 행진'''으로도 알려져 있다. 자비스 행진은 점의 개수 ''n''과 볼록 껍질을 이루는 점의 개수 ''h''에 대해 O(''nh'')의 시간 복잡도를 갖는다. 따라서, 볼록 껍질을 찾는 다른 알고리즘들과 비교해 보았을 때 이 알고리즘의 실제 성능은 ''n''이 작거나 ''h''가 ''n''에 비해 매우 작을 것으로 예상될 때 좋은 성능을 보이게 된다. 일반적인 경우에 이 알고리즘은 다른 알고리즘보다는 저조한 성능을 발휘한다.[1] 내부 루프는 집합 ''S''의 모든 점을 확인하고, 외부 루프는 껍질의 각 점에 대해 반복한다. 따라서 총 실행 시간은 O(nh)이다. 실행 시간은 출력 크기에 따라 달라지므로 자르비스 행진은 출력 의존적인 알고리즘이다. 그러나 실행 시간은 껍질 꼭지점의 수에 선형 시간으로 의존하기 때문에 껍질 꼭지점의 수 ''h''가 log ''n''보다 작을 때만 그레이엄 스캔과 같은 O(n log n) 알고리즘보다 빠르다. 또 다른 볼록 껍질 알고리즘인 찬의 알고리즘은 그레이엄 스캔의 로그 의존성과 선물 포장 알고리즘의 출력 민감도를 결합하여 점근적 실행 시간 O(n log h)을 달성하여 그레이엄 스캔과 선물 포장 모두를 개선한다.
2. 1. 알고리즘
선물 포장 알고리즘은 점들이 일반적인 위치에 있다고 가정한다. 즉, 어떠한 세 개의 점도 동일 선상에 위치하지 않는다. 일직선상의 점들을 처리하기 위해, 극점 (볼록 껍질에 포함된 선분의 끝점들)에 대해서만 선택하거나, 볼록 껍질 상의 모든 점에 대해 선택하는 방법 등이 있다. 알고리즘의 완벽한 구현은 볼록껍질이 하나 또는 두개의 정점만을 갖는 퇴화된 경우도 처리할 수 있어야 하며, 입력 데이터와 계산 과정에서 산술 정밀도의 제한도 해결해야 한다.선물 포장 알고리즘은 단계 ''i'' = 0 과 볼록 껍질에 포함되는 점 ''p0'' 에서 시작한다. 만약 pi가 가장 왼쪽에 있다면 모든 선들이 직선 ''pi p+1''의 오른쪽에 있도록 pi+1을 고를 수 있으므로 pi는 볼록껍질에 포함되는 점이 된다. 이러한 점 pi+1 을 찾기 위해 ''pi'' 를 극좌표의 중심으로 하고 반직선 pi pi+1을 시초선으로 하여 각 점의 극 각도를 비교하는데에는 O(''n'')시간이 걸린다. ''i'' 에 1을 더하고 ''ph'' = ''p0'' 을 만족할 때까지 h 단계를 거쳐 볼록 껍질을 구한다. 이차원에서 선물 포장 알고리즘은 점들의 집합에 실을 감는것(혹은 포장지를 감는 것)과 비슷하다.
이러한 접근은 더 높은 차원으로 확장될 수 있다.
2. 2. 의사 코드
자비스(S) 알고리즘의 의사 코드는 다음과 같다.:S는 점들의 집합
:pointOnHull = S 의 가장 왼쪽 점 // 볼록 껍질 CH(S)의 부분임이 보장된 점
:i=0
:반복
::P[i]=pointOnHull
::endpoint=S[0] // 껍질 위의 간선 후보중 초기 끝점
::1부터 |S| 까지 j 반복
:::if (endpoint==pointOnHull) 또는 (S[j]의 끝점이 P[i]의 왼쪽에 있을 때)
::::endpoint = S[j] //더 많이 왼쪽으로 돌게 되면 endpoint를 갱신함
::i = i + 1
::pointOnHull = endpoint
:endpoint == P[0]일 때까지 반복 //첫번째 껍질점을 포장하기
2차원 경우의 의사 코드는 다음과 같다. S는 볼록 껍질을 계산할 점들의 배열이다. 미리 볼록 껍질의 꼭짓점에 오지 않는 점들을 제거해 두면 계산량을 줄일 수 있다. L은 가변 길이 배열로, 여기에 볼록 껍질 꼭짓점의 좌표가 들어간다. A, B, C는 점이다. |AB|는 AB의 거리이다. 2차원 외적은 x1 y2 - x2 y1로 계산한다.
:A = S 중에서, 가장 y 좌표가 작은 점의 집합에서, 그 중에서 가장 x 좌표가 작은 점
:'''do''' {
::L에 A를 추가
::B = S[0]
::'''for''' i = 1 '''to''' S의 크기 - 1 {
:::C = S[i]
:::'''if''' (B == A) {
::::B = C
:::} '''else''' {
::::v = AB와 AC의 외적
::::'''if''' (v > 0 또는 (v == 0이고 |AC| > |AB|)) {
:::::B = C
::::}
:::}
::}
::A = B
:} '''while''' (A != L[0])
3. 시간 복잡도
안쪽 반복은 점들의 집합 S의 모든 점에 대하여 검사하고, 바깥쪽 반복은 껍질의 각 점에 대해 반복하므로 총 시간 복잡도는 O(nh)이다. 실행 시간은 출력의 크기에 따라 달라지기 때문에 자비스의 행진은 출력 민감 알고리즘이다.
껍질 정점의 개수 ''h'' 가 log ''n'' 보다 작을 때에는 실행시간이 O(n log n)인 그레이엄 스캔 알고리즘보다 빠르게 작동할 수 있다. 찬의 알고리즘은 선물 포장 알고리즘에 그레이엄 스캔의 로그 의존성을 결합하여 두 알고리즘보다 향상된 점근 실행 시간 O(n log h)를 가진다.
4. 고차원으로의 확장
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com