Geometric Approximation Algorithms(Sariel Har-Peled 저)의 1장 내용입니다.
Preliminaries
- 특정 width $r > 0$을 가지는 Grid는 아래 함수로 정의
$$ \begin{align*} G_r : \mathbb{R}^2 &\rightarrow (r\mathbb{N})^2 = {(ri, rj) : i, j \in \mathbb{N}} \ (x, y) &\mapsto ([\frac{x}{r}]r, [\frac{y}{r}]r) \end{align*} $$
$G_r$은 평면 공간을 정사각형 영역으로 분할하는데, 각 영역을 cell이라 부른다.
$3 \times 3$ 개의 연속한 grid cell을 grid cluster라고 정의
각 cell은 idx를 가진다($\text{id}(p) = (\frac{x}{r}, \frac{y}{r})$)
정점 $p = (x, y) \in \mathbb{R}^2$에 대해 $G_r(p) \in (r\mathbb{N})^2$
점 집합 $P = (p_1, p_2, \cdots, p_n)$에 대해 양방향 접근 가능
- 주어진 점 $p_i$가 소속된 cell 계산
- 특정 grid에 소속된 점 enumerate
- perfect hashing 가정
최단거리 쌍 찾기(Closest Pair)
그림에서 빨간색 점 두개가 최단거리를 가짐.
- $\mathcal{CP}(P) = \min_{p, q \in P}{\| p - q \|}$
- n개의 점 중 거리가 가장 짧은 두 개의 점을 찾기
- naive한 접근 : 반복문 -
for p in P, q in P- $O(n^2)$
- 결정 문제 풀기
- $\mathcal{CP}(P) \le r$
- Grid 쓰면 선형 시간 안에 풀 수 있어
- 결정 문제에서 계산 문제로 올리기
- 정점 시퀀스 $P = \langle p_1, p_2, \cdots, p_n \rangle$
- 부분 문제의 정답 $r_i = \mathcal{CP}(\{ p_1, p_2, \cdots, p_i \} )$
- 당연히 $r_{i+1} \le r_i$
- $r_i$와 $p_{i+1}$로 $r_{i+1}$ 구하기
- grid $G_{r_i}$에 $p_{i+1}$ 삽입하고, cell $G_{r_i}(p_{i+1})$ 내부 및 주변 정점들과 거리 비교 - $O(1)$
- $r_{i+1} = r_i$이면 자료구조 유지 = $O(1)$
- $r_{i+1} \lt r_i$이면 자료구조 다시 만들어야 = $O(n)$
- $r_i$가 $k$번 줄어든다면 총 $O(nk)$ 시간 소요 예상
- Brute-Force보다 느린거 아니냐
- 근데 아님 ㅋ
$$ \begin{align*} R &= T_\text{base} + \sum_{i = 2}^{n} (T_\text{step}(i) + X_i T_\text{reconstruction}(i)) \ &= 1 + \sum_{i = 2}^{n} (1 + X_i \cdot i) \end{align*} $$
그리고 $R$의 기댓값은
$$ \begin{align*} E[R] &= E[1 + \sum_{i = 2}^{n} (1 + X_i \cdot i)] \ &= 1 + (n - 1) + \sum_{i=2}^{n} (i \cdot E[X_i]) \ &= n + \sum_{i=2}^{n} (i \cdot Pr[X_i = 1]) \ &= n + \sum_{i=2}^{n} (i \cdot Pr[r_i \lt r_{i - 1}]) \end{align*} $$
고정된 $P_i = { p_1, p_2, \cdots, p_i }$에 대해 $p_i$가 최단거리 쌍에 포함될 확률은 $\le 2 / i$이다. 따라서 $Pr[r_i \lt r_{i-1}] \le 2 / i$이고, 이를 수식에 대입하면 $$ \begin{align*} E[R] &= n + \sum_{i=2}^{n} (i \cdot \frac{2}{i}) \ &= n + 2n = 3n \in O(n) \end{align*} $$ 이므로 기대 실행 시간은 입력에 선형 비례함.
- 이야깃거리
- grid update는 평균적으로 $O(\log{n}) \ni \Sigma_{i}(2/i)$회 일어남
- 점의 갯수가 많아질수록 빈도 하락
- $\mathcal{CP} \geqslant \mathit{ElmUniq}$ : $y = 0$에다가 정사영
- $\mathit{ElmUniq}(\{ s_1, s_2, \cdots, s_n \})$ : $1 \ge i \gt j \ge n : s_i = s_j$를 만족하는 $i, j$ 존재여부
- Comparison based에서 Element Uniqueness(distinctness) 문제는 $\Omega(n \log{n})$
- hash, 정수화, 랜덤화를 통한 계산 능력 상승
- grid update는 평균적으로 $O(\log{n}) \ni \Sigma_{i}(2/i)$회 일어남
k-덮개 원반($k$-Enclosing Disk) 문제의 느린 2-근사 알고리즘
$D_\text{opt}(P, k)$ : $P$의 정점 중 $k$개를 포함하는 가장 작은 반지름의 원
$r_\text{opt}(P, k)$ : $D_\text{opt}(P, k)$의 반지름
$m \in O(n / k)$개의 horizontal line $h_1, h_2, \cdots, h_m$을 위에서 아래로 그리되, 인접한 직선 사이 공간에는 $k / 4$개 이하의 정점만이 있도록 분포
$m$개의 vertical line $v_1, v_2, \cdots, v_m$을 비슷하게 그림
선형 시간 안에 median 찾는 기법을 사용하면 위 $m$개의 직선을 찾는 데 $O(n log (n/k))$ 시간 소요
$h_i, v_j$에서 유도된 non-uniform grid $G$
$X = \{ h_i \cap v_j : 1 \le i, j \le m \}$
원반 $D_\text{opt}(P, k)$의 중심을 $u$라고 부르고, $u$가 속한 cell을 $c$라고 하자.
그러면 원반이 네 귀퉁이 중 하나 이상을 포함하고 있어야 한다.
- 만약에 안 그렇다면 원이 포함할 수 있는 정점 수 $\le k/2$
optimal case의 원반을 포함하는 원반 구하기
- 원반의 중심을 $X$ 위에서 찾는다 - $O(m^2)$
- 최악의 경우 원반을 포함하는 크기의 반지름을 잡는다
- 이 때 2근사가 됨(pf. 현재 반지름 \le 원래 반원 지름)
- 정점을 고정한 다음에는 n개의 정점과 거리 계산, k번째로 가까운 원소까지 거리로 변경 - $O(n)$ (quick sort 변형)
- 이야깃거리
- 해의 후보가 $O(n^3)$ - 2개의 정점(가로축, 세로축 pivot), 축의 교차점에서 $k$번째로 가까운 점
- $k \approx O(n)$이면 실행시간이 선형에 근접
- $k$를 고정하고 $n$을 줄여도 되겠네?
- $k=n$일 때의 문제를 minimum enclosing circle이라 부름
- 정확한(exact = 1-approx) 선형시간 알고리즘 존재
- $\sqrt{2}$-approx는 걍 bounding rectangle을 포함하는 가장 작은 원 구하면 충분
k-덮개 원반($k$-Enclosing Disk) 문제의 선형 시간 2-근사 알고리즘(draft)
- idea : n개의 정점 집합을 타노스 -> k개 이하로 줄어들 때까지 반복($P_m, P_{m-1}, \cdots, P_1$)
- $P_1$에 대해 위의 느린 알고리즘 적용 - $O(n)$, $k$ 크기의 grid 만들어 정점 관리
- $P_2$에서 추가된 정점을 grid에 추가
- cell 안에 정점이 $5k$개를 초과하면 그 정점 수에 대해 알고리즘 적용
- 알고리즘의 업데이트 기대 횟수가 $O(log n)$, 정점 수가 적은 초기에 업데이트 빈번히 일어나는 특성
- $O(n)$ 기대 실행시간