1. Terminology Intersection graph from Wikipedia 평면 위의 도형으로부터 (Geometric) intersection graph를 유도할 수 있다. 그래프의 정점은 각 도형에 대응한다. 그리고, 두 정점에 대응하는 두 도형이 교차할 때 두 점 사이의 간선이 있다. Unit disk graph from Wikipedia 교차 그래프의 특수한 예시로 Unit disk graph(이하 UDG)가 있다. UDG는 동일한 반지름을 가진 원으로 구성된 intersection graph이다. UDG의 정점은 각 원의 중심 좌표로 정의된다. 그리고, 중심을 기준으로 만든 두 단위원이 교차할 때 중심을 이은 선분을 간선으로 취급한다. ...

Problem Definition 2차원 공간에서의 polygonal domain $\Gamma = { \Gamma_1, \Gamma_2, \cdots, \Gamma_h }$를 생각하자. 더 정확히 말하자면, $h$개의 서로 겹치지 않는 다각형 장애물이 있고, 이 도형들이 가진 정점의 총 갯수는 $\sum_i{|\Gamma_i|} = n$이라 가정한다. 어떤 선분 $s$가 주어졌을 때, 선분을 수직 방향으로 평행이동해서 (위, 아래로) 가장 먼저 닿는 다각형의 index와 교차하는 점을 구하여라. ($\tilde{O}(n + h^2)$ preprocessing / storage, $O(\log^c n)$ query) Related Works Segment dragging query는, 주어진 선분을 움직여서 가장 먼저 마주치는 점을 찾는 문제이다. 1988년 Chazelle이 horizontal segment에 대한 dragging query를 $O(n \log n)$ preprocessing, $O(n)$ storage로 $O(\log n)$ 시간 안에 답하는 알고리즘을 소개했다. ...

Haitao 선생님께서 키 문제를 풀어버려서 contribution이 날아갔다. Problem Polygonal domain $\mathcal{P}$와, free space 위의 정점 $s$가 주어졌다고 가정하자. shortest path to a segment query(SPSQ)는 free space 위의 간선 $\ell$이 주어지면 $s$에서 $\ell$까지의 최단 거리를 반환하는 문제이다. 짧게 쓰면 아래와 같다. $$ (\mathcal{P}, s) \mapsto \left( \ell \mapsto | \pi_\mathcal{P}(s, \ell) | := \min_{t \in \ell}| \pi_\mathcal{P}(s, t) | \right) $$ 목표 : $\tilde{O}(n + h^2)$ preprocessing, storage & $O(\log^c n)$ queries Strategy 1. Extended Corridor & Extended Ocean Chen, Wang의 Extended Corridor structure를 구성한다. [Chen, 2015] ...

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$가 있다면 이야기가 달라진다. ...

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$ ...