사용자 도구

사이트 도구


ps:이론:볼록_껍질

볼록 껍질 (Convex Hull)

개요

  • 정의는 '모든 점을 포함하는 가장 작은 볼록다각형' 이다.
    • 작다는 것은, 면적을 기준으로 해도 되고, 둘레의 길이를 기준으로 해도 된다.
  • 문제에서 주어지는 다른 표현들로는 이런 것들이 있다.
    • 임의의 점 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)

고차원으로 확장

토론

댓글을 입력하세요:
Q M​ O D M
 
ps/이론/볼록_껍질.txt · 마지막으로 수정됨: 2023/05/26 07:43 저자 teferi