1983 Meggido의 parametric search 기법을 소개한다. 경시대회에서 사용하는 기법과는 다른 것 같다. 알고리즘을 설계할 때 지금도 쓰이는 기법인데, 한글로는 검색이 안 되어서 한 번 적어본다.

$f_a : \mathbb{R} \rightarrow {0, 1}$을 아래와 같이 정의하자.

\[f_a(x) = \left\{ \begin{array}{ll} 1 & x \le a \\ 0 & x > a \end{array} \right.\]

$a \in \mathbb{R}$를 모르는 monotone 함수 $f$를 유한 번 테스트해서 $a$를 알 수 있을까? 이진 탐색을 써서 Cauchy 수열을 만들 수는 있겠지만, $a = n / 2^m$ 꼴이 아닌 이상 유한 번의 실행으로 값을 단정할 수는 없다. 실수 값을 해 집합(solution space)으로 가지는 일반적인 함수의 경우, 죽었다 깨어나도 블랙박스 테스트만으로 정확한 해를 구할 수는 없다. 대신, $x$를 받아 유한 번의 (낮은 차수 다항식의) 비교 연산을 실행하고, 계산 결과 $f(x)$를 반환하는 알고리즘 $A$가 있다면 이야기가 달라진다.

$A$를 실행하는 데 걸리는 최대 시간을 $T_A$라 하자. 특정 시점에서 실행하는 다항식 비교를 $p(x) \ge 0$이라 할 때, $p(x) = 0$을 만족하는 $x$에서만 실행 흐름이 바뀌게 된다. 비교 연산 바탕의 결정 문제는 실행 분기가 바뀔 때 답이 바뀔 수 있으므로, 이런 구간들을 잘 따라가면 답안을 구할 수 있다는 게 논지이다.

serialsearch

저자는 알고리즘을 generic하게 실행한다는 표현을 쓴다. 값을 입력받아 알고리즘을 실행하는 게 아니라, 찾고자 하는 제어 흐름(control flow)에 맞는 해의 구간(interval)을 들고 함숫값이 1에서 0이 되는 구간을 좁혀가는 방법을 쓴다. 각 분기점에서 함숫값이 변하는 구간을 포함하는 인접한 두 해를 이진 탐색한다. 기존 해 구간을 $(x_i, x_{i+1})$과의 교집합으로 업데이트하면서, 탐색 영역은 점점 좁아지게 된다.

이렇게 논의한 방법으로, 알고리즘을 generic하게 실행하는 시점마다 $O(d \log d + T_A \log d)$의 시간을 소요하게 된다. 다항식의 최대 차수가 상수로 고정되어 있다면, $O(T_A)$의 시간이 소요된다. 따라서 parametric search의 총 실행 시간은 $O(T_A^2)$가 된다.

parallelsearch

똑같은 문제를 푸는 병렬 알고리즘 $B$가 있으면, 시간 복잡도를 크게 낮출 수 있다. $p$개의 프로세서를 사용하여 $f$를 계산하는 데 $T_B$ 시간이 걸린다고 가정하자. 병렬 실행이므로 각 시점마다 많아야 $p$개의 다항식 비교 연산이 동시 실행될 수 있으며, 동시에 실행되는 연산은 상호 영향을 주지 않는다. 이 점을 이용하면 $p$개 다항식들의 해들을 합쳐서 이진 탐색을 할 수 있다. 단일 프로세서에서 이를 실행한다 치자. 병렬 알고리즘의 각 시점마다 $O(p + T_A \log p)$만큼의 시간이 소요되고, 총 실행 시간은 $O(T_B(p + T_A \log p))$가 된다.

보통은 $T_B T_A \log p$가 시간복잡도를 지배하게 된다. log로 들어가는 병렬 프로세서를 최대한 늘려서 $T_B = O(\log^c n)$ 꼴로 만들 수 있으면 남는 장사가 된다.

계산 기하학의 꽤 많은 문제를 parametric search로 풀 수 있다. 92년도에 출판된 Applications of Parametric Searching in Geometric Optimization에 기재된 예를 들면:

  • 주어진 simple polygon 안에 들어가는 가장 긴 선분의 길이 찾기. 도형의 정점을 절반씩 갖도록 현(chord) $e$를 그어 분할한 뒤, $e$를 지나면서 길이 $d$ 이상의 선분이 도형 안에 들어가는지 결정하는 문제로 변환한다. 이 문제를 $O(n^{8/5 + \epsilon})$개의 병렬 프로세서로 $O(\log^2 n)$ 안에 풀 수 있고, 다른 과정의 시간을 subsume하게 된다. 따라서 전체 실행 시간은 $O(n^{8/5 + \epsilon})$이다.
  • Ray shooting. 광선이 처음으로 장애물과 부딪히는 점을 찾는 문제. 광선을 $\rho = {x(t) = x_0 + t \vec{v} : t \in \mathbb{R}^+}$로 표기할 수 있고, $\overline{x_0 x_t}$이 장애물과 겹치는 지의 문제는 monotone decision이 된다.
  • 최소폭 고리(minimum-width annulus).
  • 두 도형 사이의 하우스도르프 거리(Hausdorff distance)
  • 구(sphere) 사이의 상호 가시성(mutual visibility)
  • segment center, 2-center, extremal polygon containment 등

References

[1] Agarwal, P. K., & Matoušek, J. (1993). Ray shooting and parametric search. SIAM Journal on Computing, 22(4), 794-806.

[2] Agarwal, P. K., Sharir, M., & Toledo, S. (1994). Applications of parametric searching in geometric optimization. Journal of Algorithms, 17(3), 292-318.

[3] Megiddo, N. (1983). Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM (JACM), 30(4), 852-865.