The Power of Grid
Geometric Approximation Algorithms(Sariel Har-Peled 저)의 1장 내용입니다.
Preliminaries
- 특정 width $r > 0$을 가지는 Grid는 아래 함수로 정의
- $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 쓰면 선형 시간 안에 풀 수 있어
$\mathcal{CP}(P) \le r$ 여부 계산하는데 선형 시간 소요
$G_r(P)$ 계산하는 데 O(n)이 걸린다.
각 cell을 3x3 크기의 정사각형들로 분할하자.
2개 이상의 점이 들어가는 사각형이 있으면 True를 리턴하고 종료.
($d(x, y) \le \sqrt{2}r / 3$)
모든 cell에 대해 위를 실행하고 종료 안 되었다면 각 cell에 많아야 9개의 정점이 있다는 이야기가 됨. 인접한 cell의 정점들과 거리를 측정. 기껏해야 $8 \times 9$개의 정점들과 거리 측정이므로 cell당 최대 $9 \times (8 \times 9) = 648$번의 거리 계산 여기서도 거리가 r 미만인 정점 쌍을 발견시 즉시 리턴 cell의 갯수가 $O(n)$이므로 총 연산시간도 linear.
Correctness: cell 내부 및 인접 탐색을 통해 r보다 작은 거리의 정점을 탐색하는 방식이다. r보다 작은 거리의 두 정점이 반드시 같은 cell에 있거나 인접한 cell에 소속되어 있으므로 OK
모든 cell에 대해 위를 실행하고 종료 안 되었다면 각 cell에 많아야 9개의 정점이 있다는 이야기가 됨. 인접한 cell의 정점들과 거리를 측정. 기껏해야 $8 \times 9$개의 정점들과 거리 측정이므로 cell당 최대 $9 \times (8 \times 9) = 648$번의 거리 계산 여기서도 거리가 r 미만인 정점 쌍을 발견시 즉시 리턴 cell의 갯수가 $O(n)$이므로 총 연산시간도 linear.
Correctness: cell 내부 및 인접 탐색을 통해 r보다 작은 거리의 정점을 탐색하는 방식이다. r보다 작은 거리의 두 정점이 반드시 같은 cell에 있거나 인접한 cell에 소속되어 있으므로 OK
- 결정 문제에서 계산 문제로 올리기
- 정점 시퀀스 $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보다 느린거 아니냐
- 근데 아님 ㅋ
$\mathcal{CP}(P)$를 평균 선형 시간(Expected linear time) 안에 구할 수 있다.
집합 $P : \| P \| \ge 3$의 무작위 순열을 $\langle p_1, p_2, \cdots, p_n \rangle$이라 하자.
$r_2 = \| p_1 - p_2 \|$을 계산하고, 이후 앞의 incr construction을 사용하자.
실행 시간을 계산하기 위해 확률 변수 $X_i$를
$r_i \neq r_{i - 1}$이면 1이고 같으면 0이라 정의하자.
이때 실행시간은 아래 변수 $R$에 비례할 것이다.
$$
\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 (n/k)^2)$ 시간 안에 $P$의 정점을 $k$개 포함하는 반원 $D$를 찾을 수 있고,
$D$의 반지름은 $D_\text{opt}(P, k)$의 두배 이하이다.
- 이야깃거리
- 해의 후보가 $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)$ 기대 실행시간