The Power of Grid

Geometric Approximation Algorithms(Sariel Har-Peled 저)의 1장 내용입니다.

Preliminaries

• 특정 width $r>0$을 가지는 Grid는 아래 함수로 정의

$$\begin{array}{rl}{G}_r:{\mathbb{R}}^2& \to (r\mathbb{N}{)}^2=\{(ri,rj):i,j\in \mathbb{N}\}\\ (x,y)& \mapsto ([\frac{x}{r}]r,[\frac{y}{r}]r)\end{array}$$

• $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)

그림에서 빨간색 점 두개가 최단거리를 가짐.

• $$\begin{gathered} \mathcal{C}\mathcal{P}(P)={\min }_{p,q\in P} \\ |p-q \\ | \end{gathered}$$
  • n개의 점 중 거리가 가장 짧은 두 개의 점을 찾기
  • naive한 접근 : 반복문 - for p in P, q in P - $O(n^2)$
• 결정 문제 풀기
  • $\mathcal{C}\mathcal{P}(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

• 결정 문제에서 계산 문제로 올리기
  • 정점 시퀀스 $P=⟨p_1,p_2,\cdots ,p_n⟩$
  • 부분 문제의 정답 $$\begin{gathered} r_i=\mathcal{C}\mathcal{P}( \\ {p}_1,p_2,\cdots ,p_i \\ ) \end{gathered}$$
  • 당연히 $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}<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{array}{rl}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{array}$$

그리고 $R$의 기댓값은

$$\begin{array}{rl}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<r_{i-1}])\end{array}$$

고정된 $P_i=\{p_1,p_2,\cdots ,p_i\}$에 대해 $p_i$가 최단거리 쌍에 포함될 확률은 $\le 2/i$이다. 따라서 $Pr[r_i<r_{i-1}]\le 2/i$이고, 이를 수식에 대입하면

$$\begin{array}{rl}E[R]& =n+\sum _{i=2}^n(i\cdot \frac{2}{i})\\ & =n+2n=3n\in O(n)\end{array}$$

이므로 기대 실행 시간은 입력에 선형 비례함.

• 이야깃거리
  • grid update는 평균적으로 $O(\log n)\ni {\Sigma }_i(2/i)$회 일어남
    • 점의 갯수가 많아질수록 빈도 하락
  • $\mathcal{C}\mathcal{P}⩾ElmUniq$ : $y=0$에다가 정사영
    • $$\begin{gathered} ElmUniq( \\ {s}_1,s_2,\cdots ,s_n \\ ) \end{gathered}$$ : $1\ge i>j\ge n:s_i=s_j$를 만족하는 $i,j$ 존재여부
  • Comparison based에서 Element Uniqueness(distinctness) 문제는 $\Omega (n\log n)$
  • hash, 정수화, 랜덤화를 통한 계산 능력 상승

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(nlog(n/k))$ 시간 소요

• $h_i,v_j$에서 유도된 non-uniform grid $G$

• $$\begin{gathered} X= \\ {h}_i\cap v_j:1\le i,j\le m \end{gathered}$$

• 원반 $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(logn)$, 정점 수가 적은 초기에 업데이트 빈번히 일어나는 특성
• $O(n)$ 기대 실행시간