# Plane Sweeping

• 2026년 7월 9일 알고리즘
  볼록 껍질 ③ — Plane Sweeping과 동적 갱신

  점을 하나씩 더해 가며 볼록 껍질을 유지하는 두 문제를 다룬다. 점을 x좌표 순으로 추가하는 Plane Sweeping(O(N²)에서 균형 트리로 O(N log N))과, 완성된 껍질에 점이 계속 추가되는 동적 볼록 껍질이다.

• 2026년 7월 2일 알고리즘
  가장 가까운 점 쌍 ③ — Plane Sweeping과 균형 이진 탐색 트리

  2편과 같은 O(n log n)에 다른 시선으로 닿는다. 점을 x좌표 순으로 훑으며 폭 D 안의 점만 균형 BST(std::set)에 담는 Plane Sweeping으로, y좌표 [y-D, y+D] 구간만 조회한다. 후보가 상수 개임을 보여 전체 O(n log n)을 유도한다.