맨위로가기

그레이엄 스캔

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

그레이엄 스캔은 주어진 점 집합의 볼록 껍질을 구하는 알고리즘으로, 계산 기하학 분야에서 사용된다. 이 알고리즘은 먼저 y좌표가 가장 작은 점을 찾고, 이 점을 기준으로 나머지 점들을 정렬한다. 정렬된 점들을 순차적으로 처리하면서, 외적을 이용해 좌회전 또는 우회전을 판별하여 볼록 껍질에 포함될 점들을 결정한다. 시간 복잡도는 O(n log n)이며, 점들을 정렬하는 단계에서 소요된다. 부동 소수점 산술을 사용할 때 수치적 강건성 문제가 발생할 수 있으며, 이를 해결하기 위한 연구도 진행되었다.

2. 알고리즘

PAB와 ABC는 반시계 방향이지만, BCD는 그렇지 않다. 알고리즘은 이러한 상황을 감지하고 반시계 방향이 될 때까지(위 그림에서 ABD) 이전에 고른 점을 버린다.


그레이엄 스캔은 볼록 껍질을 찾는 알고리즘으로, 다음 단계를 거친다.

먼저, 주어진 점들 중 y 좌표가 가장 작은 점을 찾는다. 만약 y 좌표가 같은 점이 여러 개 있다면, 그 중에서 x 좌표가 가장 작은 점을 선택한다. 이 점을 P라고 하고, 이 단계는 O(n) 시간이 걸린다.

다음으로 P를 기준으로 다른 점들을 x축에 대한 각도가 증가하는 순서로 정렬한다. 이 과정에는 힙 정렬 (O(n log n))과 같은 일반적인 정렬 알고리즘을 사용할 수 있다. 각도를 직접 계산하는 대신, 구간 [0, \pi]에서 단조 증가하는 함수를 이용할 수 있다. 예를 들어, 스칼라곱으로 계산되는 코사인이나 P에서 점까지의 직선의 기울기를 사용할 수 있다. 수의 정밀도가 중요한 경우에는 외적의 부호를 이용하여 상대적인 각도 (좌회전, 우회전)를 판정할 수 있다.

정렬된 점들을 순차적으로 처리하며, 각 점마다 바로 앞의 두 점과 함께 세 점이 반시계 방향(좌회전)인지, 시계 방향(우회전)인지 판정한다. 우회전할 경우 맨 끝에서 두 번째 점은 볼록 껍질에 속하지 않으므로 제거한다. 좌회전이 될 때까지 이 과정을 반복한다. 세 점 P_1 = (x_1, y_1), P_2 = (x_2, y_2), P_3 = (x_3, y_3)에 대해, (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1) 값이 양수이면 반시계 방향, 음수이면 시계 방향, 0이면 일직선 상에 있다.

이 과정을 시작점 P로 돌아올 때까지 반복하면 알고리즘은 종료되고, 남은 점들이 볼록 껍질을 구성한다.

2. 1. 점 정렬



먼저 주어진 점들 중에서 y 좌표가 가장 작은 점을 찾는다. y 좌표가 같은 점이 여러 개 있다면, 그중에서 x 좌표가 가장 작은 점을 선택한다. 이 점을 기준점 P라고 한다. 이 단계는 점의 개수를 n이라고 할 때 O(n) 시간에 수행된다.[1]

다음으로, 점 P를 기준으로 다른 점들을 x축에 대한 각도가 증가하는 순서로 정렬한다. 이 과정에는 힙 정렬 (O(n log n))과 같은 일반적인 정렬 알고리즘을 사용할 수 있다.[2]

각도 순으로 정렬할 때 각도를 직접 계산할 필요는 없다. 구간 [0,\pi]에서 단조 증가하는 함수를 사용할 수 있다. 내적을 이용해 코사인을 쉽게 계산하거나, P에서 점까지의 직선 기울기를 사용할 수도 있다. 수의 정밀도가 중요하다면, 외적의 부호를 통해 상대적인 각도(좌회전, 우회전)를 판정할 수 있다.[3]

만약 여러 점이 동일한 각도를 가진다면, 맨해튼 거리나 체비쇼프 거리 (점들이 같은 반직선 상에 있기 때문에 유클리드 거리보다 쉽게 계산 가능)를 이용하여 거리가 더 먼 점을 제외하고 나머지 점들은 제거한다.[4]

2. 2. 볼록 껍질 찾기



그레이엄 스캔 알고리즘은 먼저 y좌표가 가장 작은 점을 찾는다. y좌표가 같은 점이 여러 개라면, 그중 x좌표가 가장 작은 점을 선택한다. 이 점을 ''P''라고 한다.

다음으로, 점들을 ''P''를 기준으로 x축과 이루는 각도가 커지는 순서로 정렬한다. 힙 정렬과 같은 정렬 알고리즘을 사용할 수 있다. 각도를 직접 계산하는 대신, 구간 [0, \pi]에서 단조 증가하는 함수를 이용할 수 있다. 예를 들어, 스칼라곱으로 계산되는 코사인 값이나 P에서 각 점까지의 기울기를 사용할 수 있다. 정밀도가 중요한 경우, 외적의 부호를 이용하여 상대적인 각도(좌회전, 우회전)를 판단할 수 있다.

알고리즘은 정렬된 점들을 순서대로 처리한다. 각 점에 대해, 직전 두 점과 함께 세 점이 반시계 방향(좌회전)인지, 시계 방향(우회전)인지 확인한다. 만약 시계 방향이면, 직전 점은 볼록 껍질 내부의 점이므로 제거한다. 반시계 방향이 될 때까지 이 과정을 반복한다. 세 점 P_1 = (x_1, y_1), P_2 = (x_2, y_2), P_3 = (x_3, y_3)에 대해, (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1) 값이 양수이면 반시계 방향, 음수이면 시계 방향, 0이면 일직선 상에 있다.

이 과정을 시작점 ''P''로 돌아올 때까지 반복하면 알고리즘이 종료되고, 남은 점들이 볼록 껍질을 구성하는 점들이 된다.

3. 시간 복잡도

점들을 정렬하는 데 O(''n'' log ''n'') 시간이 소요된다. 반복문 부분은 각 점마다 뒤로 돌아가서 이전 점이 "우회전"을 하는지만 확인하며, 각 점을 최대 두 번까지만 확인하기 때문에 O(''n'')이다. 각 점은 "좌회전"의 point|점영어 (x_2, y_2)로 한 번, "우회전"의 point|점영어 (x_2, y_2)로 한 번 나타난다. 정렬에 필요한 시간 복잡도가 볼록 껍질을 계산하는 시간보다 길기 때문에 전체 시간 복잡도는 O(''n'' log ''n'')이다.[1]

4. 의사 코드

아래의 코드는 `ccw` 함수를 사용하며, `ccw` > 0이면 세 점이 반시계 방향으로, `ccw` < 0이면 시계 방향으로 꺾이며, `ccw` = 0이면 한 직선 위에 있다. (실제 응용에서는 좌표가 임의의 실수일 경우 이 함수가 부동소수점 비교를 정확히 수행해야 하며, "거의" 한 직선 위에 있는 점에서 발생하는 수치적 특이점에도 유의해야 한다.)

계산 결과를 `stack`에 저장한다.

```

'''let''' points '''be''' 점들의 목록

'''let''' stack = empty_stack()

'''find''' 가장 낮은 y좌표와 가장 왼쪽에 있는 점, P0이라고 부름

'''sort''' P0을 기준으로 극각으로 점들을 정렬한다. 여러 점이 동일한 극각을 갖는 경우 가장 먼 점만 유지한다.

'''for''' point '''in''' points:

# 이 점에 도달하기 위해 시계 방향으로 회전하는 경우 스택에서 마지막 점을 팝한다.

'''while''' '''count''' stack > 1 and '''ccw'''(next_to_top(stack), top(stack), point) <= 0:

'''pop''' stack

'''push''' point '''to''' stack

'''end'''

```

이제 스택에는 볼록 껍질이 포함되어 있으며, 여기서 점들은 반시계 방향으로 정렬되고 P0은 첫 번째 점이다.

여기서 `next_to_top()`은 스택을 변경하지 않고 스택 상단의 항목 바로 아래 항목을 반환하는 함수이고, 마찬가지로 `top()`은 최상위 요소를 반환하는 함수이다.

이 의사 코드는 ''알고리즘 소개(Introduction to Algorithms)''에서 가져온 것이다.

5. 수치적 정밀성

부동소수점 연산을 사용하는 알고리즘에서는 수치적 정밀성이 문제가 된다. 2004년 논문에서는 그레이엄 스캔을 구현할 때 사용할 수 있는 간단한 증분 전략을 분석하였다.[13] 이 논문의 목표는 알고리즘 자체를 분석하기보다는 계산기하학에서 부동소수점 계산이 어떻게 실패할 수 있는지에 대한 예시를 제공하는 것이었다.[13]

이후 D. Jiang과 N. F. Stewart는 이 논문에 부연하여 역방향 오차 분석을 통해 두 가지 결론을 도출했다. 첫째, 볼록 껍질은 well-conditioned (양호 조건) 문제이므로, 이 문제를 해결하는 알고리즘의 오차가 합리적인 범위 이내일 것이라는 점이다. 둘째, 이들은 스티븐 포춘(Steven Fortune)의 이름을 따 Graham-Fortune이라고 부르는 그레이엄 스캔의 변형 알고리즘이 유한 정밀도와 부정확한 데이터 문제를 "해결할 수 있는 최대한의 한도 내에서" 해결할 수 있음을 보였다.

6. 응용

그레이엄 스캔에서 스택을 활용하는 기법은 모든 최근접 최솟값 문제와 매우 비슷하며, 이 문제를 해결하는 병렬 알고리즘을 (그레이엄 스캔처럼) 정렬된 점들의 볼록 껍질을 효율적으로 계산하는 데도 사용할 수 있다.[12]

7. 관련 문서

참조

[1] 논문 An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set http://www.math.ucsd[...]
[2] 논문 Another efficient algorithm for convex hulls in two dimensions
[3] 서적 Computational Geometry Algorithms and Applications https://archive.org/[...] Springer Science+Business Media
[4] 간행물 Discrete and Computational Geometry: The Goodman-Pollack Festschrift Springer
[5] 논문 Optimal double logarithmic parallel algorithms based on finding all nearest smaller values
[6] 논문 Classroom examples of robustness problems in geometric computations http://hal.inria.fr/[...]
[7] 웹인용 Backward error analysis in computational geometry http://www.iro.umont[...] Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series Lecture Notes in Computer Science, pp 50–59 2017-08-09
[8] 서적 30th Annual Symposium on Foundations of Computer Science
[9] 논문 An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set http://www.math.ucsd[...]
[10] 논문 Another efficient algorithm for convex hulls in two dimensions
[11] 서적 Computational Geometry Algorithms and Applications https://archive.org/[...] Springer Science+Business Media
[12] 논문 Optimal double logarithmic parallel algorithms based on finding all nearest smaller values
[13] 논문 Classroom examples of robustness problems in geometric computations http://hal.inria.fr/[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com