# Computational Geometry

2026년 7월 15일 알고리즘
추가 설명 — 평행한 변이 만드는 동률과 대척점 쌍 열거
볼록 껍질 ⑤의 Rotating Calipers 뼈대는 평행한 변이 있어도 지름 값이 옳다. 이 글은 대척점 쌍 열거가 왜 별개 문제인지, 평행한 변이 만드는 동률과 교차 쌍을 어떻게 채우는지를 다룬다. 완전성(빠짐없음)은 얻되 유일성(중복 없음)은 얻지 못하며, 그 차이가 어디서 오는지까지 밝힌다.
2026년 7월 14일 알고리즘
볼록 껍질 ⑤ — 가장 먼 두 점과 Rotating Calipers
볼록 껍질을 도구로 써서 평면의 가장 먼 두 점(지름)을 찾는다. 가장 먼 쌍은 껍질 꼭짓점이며, 평행선을 돌리며 대척점 쌍만 훑는 Rotating Calipers로 모든 쌍 O(N²) 대신 O(N)에 얻는다.
2026년 7월 13일 알고리즘
볼록 껍질 ④ — 분할 정복과 공통 접선
점들을 절반으로 갈라 각각의 껍질을 재귀로 구한 뒤 공통 접선(common tangent)으로 잇는 분할 정복을 다룬다. 접선을 O(N)에 찾는 선형 워킹을 증명까지 따라가고, 이진 탐색을 겹쳐 O(log²N)으로 줄이는 아이디어와 그 아이디어가 아직 채우지 못한 부분을 밝힌다.
2026년 7월 10일 알고리즘
추가 설명 — 균형 트리에서 접선을 O(log N)에 찾기
볼록 껍질 ③이 미뤄둔 부분. x좌표로 정렬된 볼록 사슬을 균형 트리에 담아, 외부 점에서 그은 접선의 접점을 O(log N)에 찾는 법. 후보 꼭짓점의 두 이웃 변에 CCW를 돌려 방향을 판정하고, 그것이 왜 이진 탐색이 되는지 따라간다.
2026년 7월 9일 알고리즘
볼록 껍질 ③ — Plane Sweeping과 동적 갱신
점을 하나씩 더해 가며 볼록 껍질을 유지하는 두 문제를 다룬다. 점을 x좌표 순으로 추가하는 Plane Sweeping(O(N²)에서 균형 트리로 O(N log N))과, 완성된 껍질에 점이 계속 추가되는 동적 볼록 껍질이다.
2026년 7월 8일 알고리즘
볼록 껍질 ② — Graham Scan과 정렬 하한
Package Wrapping은 걸음마다 점 전체를 훑어 최악 O(N²)이다. Graham Scan은 각도 정렬 한 번 뒤 스택으로 좌회전만 남겨 O(N log N)에 볼록 껍질을 구한다. 정렬을 볼록 껍질로 환원해 Ω(N log N) 하한까지 확인한다.
2026년 7월 7일 알고리즘
볼록 껍질 ① — 정의, CCW, 그리고 Package Wrapping
평면의 점들을 모두 감싸는 가장 작은 볼록 다각형, 볼록 껍질(convex hull)을 구한다. O(N³) 브루트포스에서 출발해 세 점의 회전 방향을 정수 연산으로 판정하는 CCW를 유도하고, 포장지로 감싸듯 껍질을 찾는 Package Wrapping(O(NH))까지 다룬다.
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)을 유도한다.
2026년 7월 1일 알고리즘
가장 가까운 점 쌍 ② — 정렬을 유지해 O(n log n)으로
1편 O(n log²n)의 여분 log n은 combine마다 y정렬을 다시 하는 데서 나온다. 재귀가 y로 정렬된 결과를 반환하게 만들어 combine을 O(n) merge로 바꾸고, 분할은 x·순서는 y로 유지해 전체를 O(n log n)으로 끌어내린다.
2026년 6월 30일 알고리즘
추가 설명 — 왜 다음 7개만 비교하면 되는가
가장 가까운 점 쌍의 combine에서, 한 점이 옆에 있는 점을 몇 개만 비교해도 되는 이유를 쉽게 풀어 본다. 핵심은 '가까운 점은 좁은 공간에 빽빽이 들어갈 수 없다'는 것. 후보가 들어올 칸을 잘게 쪼개 세면, 비교 대상이 n과 무관한 상수(최대 7개)로 묶인다.
2026년 6월 30일 알고리즘
가장 가까운 점 쌍 ① — 분할 정복과 O(n log²n)
2차원 평면에서 가장 가까운 두 점을 찾는 문제. 모든 쌍을 보면 O(n²)이지만, 분할 정복으로 더 빠르게 풀 수 있다. x좌표로 좌우를 나눠 각 영역의 최소 거리 D를 구한 뒤, 경계의 폭 D 밴드만 합치는 과정을 보고 O(n log²n)임을 유도한다.