ps:이론:볼록_껍질
목차
볼록 껍질 (Convex Hull)
- 난이도: 플래티넘 5
- 기본 문제: 1708
- 참고 자료
개요
- 정의는 '모든 점을 포함하는 가장 작은 볼록다각형' 이다.
- 작다는 것은, 면적을 기준으로 해도 되고, 둘레의 길이를 기준으로 해도 된다.
- 문제에서 주어지는 다른 표현들로는 이런 것들이 있다.
- 임의의 점 3개로 만들어지는 삼각형들의 합집합
- 최적 시간 복잡도는 O(nlogn). O(nlogh)도 있긴 하지만..
- 널리 알려진 O(nlogn) 알고리즘 은 두가지이다.
- Graham scan 과 monotone chain
- 더 널리 알려진것? 은 Graham scan 이다
- 바닥상태에서 짜기 쉬운 것은 monotone chain이다. Graham scan은 점들의 각도정렬을 할줄 알아야 한다.
- 속도는..
- Graham scan의 각도 정렬을 ccw를 써서 하면 monotone chain보다 느리다
- Graham scan의 각도 정렬을 x/y 값을 사용하고, 최적화하면 monotone chain보다 빨라진다
- monotone chain은 upper hull과 lower hull을 각각 계산하기 위해서 모든 점을 이터레이션 하는 것을 두번 반복해야 하는데, Graham scan은 한번으로 된다.
구현
- Monotone Chain 의
- Graham Scan
Graham Scan
- 각도 정렬을 시킬때, 각도로만 정렬하는 방법과 (각도, 거리)으로 정렬하는 방법(각도가 같을때는 거리가 짧은것이 앞서도록) 이 있다.
- 기본적으로는 각도로만 정렬해도 충분하지만, 이 때에는 가장 작은 각도에 해당되는 점과 가장 큰 각도에 해당되는 점이 여러개일경우를 따로 처리해줘야 한다.
- 가장 작은 각도에 해당되는 점들 중에서는 거리가 가장 큰 점을 선택해야 한다.
- 만약 3개 이상이 점이 한 직선상에 있는 경우를 모두 볼록껍질에 포함시키기로 결정했다면, 이 점들을 거리순으로 정렬해야 한다.
- (각도, 거리)로 정렬하는 것은 가장 작은 각도에 해당되는 점과 가장 큰 각도에 해당되는 점이 여러개일때, 이것들을
예외 처리
- 같은 점이 두개 이상 있는 경우?
- 이걸 허용하면 골치아프다. 허용하지 말자
- 3개 이상이 점이 한 직선상에 있는 경우?
- 이건 처리해줘야 한다. 모든 점을 볼록껍질에 포함시킬건지, 양 끝점만 볼록껍질에 포함시킬건지를 결정해야 한다.
- 모든 점이 한 직선상에 있는 경우?
- 예외 취급 해야하나? 응
관련 문제
- 1708: 점은 100,000 개. 좌표의 범위는 40,000.
- 100,000개 정도의 점에서 convex hull을 만드는 것은 300ms정도면 돌아간다.
- 점 갯수가 좀더 많은 문제가 있어야지 성능 측정이 제대로 될거 같은데.. 그런 문제가 별로 없다.
- 22962가 그나마 점은 500,000 개, 좌표의 범위는 10^9. 인데 얘는 볼록 다각형 내부의 점 판정이 추가로 필요해서 난이도가 좀더높다
확장
Decremental convex hull
Nested convex hull
원들의 볼록 껍질
- 난이도
- O(nh)
- O(nlogn)
고차원으로 확장
ps/이론/볼록_껍질.txt · 마지막으로 수정됨: 2023/05/26 07:43 저자 teferi
토론