Separating (Non-Unit) Disk Graphs

1. Terminology

Intersection graph from Wikipedia

평면 위의 도형으로부터 (Geometric) intersection graph를 유도할 수 있다. 그래프의 정점은 각 도형에 대응한다. 그리고, 두 정점에 대응하는 두 도형이 교차할 때 두 점 사이의 간선이 있다.

Unit disk graph from Wikipedia

교차 그래프의 특수한 예시로 Unit disk graph(이하 UDG)가 있다. UDG는 동일한 반지름을 가진 원으로 구성된 intersection graph이다. UDG의 정점은 각 원의 중심 좌표로 정의된다. 그리고, 중심을 기준으로 만든 두 단위원이 교차할 때 중심을 이은 선분을 간선으로 취급한다.

Disk graph from Giannopoulos et al

Disk graph(이하 DG) 또한 여러 개의 원으로 구성되나, 반지름이 다를 수 있다. 따라서, 원 $D_i = B(x_i; r_i)$마다 $x_i$(중심 좌표), $r_i$(반지름)을 가진다. 두 원 $D_i, D_j$가 $|x_i - x_j| \le r_i + r_j$를 만족할 경우 그 사이에 간선이 있다고 본다.

그래프 간선의 가중치 차이가 없다(unweighted)고 가정한다.

2. Objective

$s, t$가 disk graph의 원 밖에 주어져 있다고 가정하자. DG 위의 원 몇 개를 잘 고르면, s에서 t로 가는 경로가 해당 집합과 부딪히게 만들 수 있다. 이러한 집합을 separator라 부른다. $s, t$를 분리하는 subset $D’ \subseteq D$가 존재하는지 확인하고, 그 최소 갯수를 구하는 문제이다.

3. Previous Works (Cabello, Milinkovic)

UDG 위의 SPT를 써서 separator 문제 풀기
minimum separator는 사이클을 포함함
$s, t$를 분할하는 cycle은 두 점을 이은 선분 $\overline{st}$와 홀수 번 겹쳐
UDG 위의 SPT root가 최적 separator soln 위에 있으면 “간선 하나 추가해 만들어지는 cycle들” 중에서 최적해 찾을 수 있다
Brute-force 보다 효과적으로 풀기 위해 선분과 point set 교차 여부 푸는 효율적 자료구조 설계
SPT 구성하면서 얻어진 distance level + 선분 좌우 + path crossing으로 점 분할,
사이에 간선 있는 set pair를 $O(n)$으로 줄여서 앞의 alg 적용 -> linearitmic for each root
이걸 모든 root마다 반복

SPT on DG?

Fig.1 from Cabello and Milinkovic

Fig.3 from Cabello and Jejcic

Cabello, Jejcic의 방법

UDG의 중심을 가지고 Delaunay triangulation을 구한다. 그리고, Delaunay 그래프 위에서 greedy하게 거리 1 이하인 이웃을 탐색하는 방법이다.

DG의 경우 Cabello, Jejcic의 방법을 그대로 적용할 수 없다. DT 위에서 가장 근접한 이웃들이 DG 간선으로 이어져있지 않을 수 있기 때문이다. 따라서 Delaunay graph 위에서 시작점이 DT 위의 어떤 이웃과도 연결되어 있지 않을 수 있고, 이 경우 DG 위에서 시작점이 연결되어 있음에도 SPT가 올바르게 만들어지지 않게 된다.

아래에 반례 예시는 DT 위에서 시작점과 이웃하는 원들이 시작점의 원과 교차하지 않는 경우이다. 이러한 경우 Cabello, Jejcic의 SPT 알고리즘은 시작점을 제외한 어떤 점도 포함하지 못한다.

• $O(n \log^9 n \lambda_6(\log n))$ 시간 안에 BFS tree를 구하는 방법이 개발되었다[5].

4. Intersection between a line segment and DG edges

선분 $\overline{st}$가 주어져 있을 때, 주어진 DG에서 $\overline{st}$와 교차하는 DG 그래프 간선이 있는지 결정하는 문제를 풀어볼 것이다.

Cabello, Milinkovic[1]의 접근법

이 문제를 풀기 위해 선분 $st$와 겹치는 두 점의 성질을 먼저 찾는다. 계산의 편의를 위해 $t$가 원점, $s$가 y축 위($>0$)에 있다고 가정하자. (만약에 그렇지 않다면 좌표평면을 적절히 회전/이동하여 위의 조건을 만들 수 있다.)

Fig.4 from Cabello and Milinkovic

$ab_i$가 $st$와 만나려면 한 점은 선분 왼쪽, 한 점은 선분 오른쪽에 있어야 한다. 왼쪽의 점 $a$에 대해, 오른쪽의 점들 $b_1, b_2, \cdots, b_n$ 중 $\overline{st}$와 만나는 $\overline{ab_i}$의 조건을 알아본다. $\overline{st}$와 $\overline{ab_i}$가 만난다는 것은 $\overrightarrow{at}$의 기울기가 $\overrightarrow{tb_i}$의 기울기보다 크면서, $\overrightarrow{as}$의 기울기가 $\overrightarrow{sb_i}$의 기울기보다 작은 것과 동치이다.

점을 입력으로 받아 $s, t$까지의 기울기를 반환하는 함수를 각각 $\phi_1, \phi_2$라 하자. 그러면, $\phi_1(a) \le \phi_1(b_i)$ 이면서 $\phi_2(a) \ge \phi_2(b_i)$를 만족하는 $b_i$만이 $\overline{st}$와 $\overline{ab_i}$가 겹치도록 한다. 이 사실을 이용하면, 선분 오른쪽의 정점 $b_i$들을 가지고 자료구조를 만들어 선분 왼쪽의 정점 $a$가 주어졌을 때 $\overline{ab_i}$와 $\overline{st}$가 겹치는 $b_i$를 효율적으로 나열할 수 있다. 이 중에서 $a$와 가장 가까운 정점 $b_i$ 까지의 거리가 1 이하인지 비교하는 것으로 문제의 답안을 구할 수 있다.

먼저 모든 정점 $b_i$를 $\phi$-plane 위의 점 $(\phi_1(b_i), \phi_2(b_i))$로 변환하고 range tree를 만든다. 그리고 2단계 range tree의 모든 node마다 nearest neighbor 자료구조를 만든다. 이 tree node에 붙은 자료구조는 주어진 점으로부터 트리의 descendants 중 가장 가까운 정점을 반환한다.

새로운 점 $a$가 주어지면 $\phi_1(a) \le \phi_1(b_i)$이면서 $\phi_2(a) \ge \phi_2(b_i)$인 정점의 묶음을 range query를 통해 구한다. 이 때 range query는 모든 점을 일일이 반환하는 게 아닌, $O(\log^2 n)$개의 마지막 레벨 range tree의 노드들을 반환한다. range tree의 leaf node는 하나의 점을, non-leaf node는 두 subtree의 점들을 포함하는 point set을 의미한다. 이 $O(\log^2 n)$개의 tree node는 $ab_i$가 $\overline{st}$와 부딪히게 하는 $b_i$의 partition이다. 각 node에서 $a$에서 가장 가까운 nearest neighbor $b_i$를 구하고, 최근접 이웃까지의 거리가 1보다 작은지 확인한다. 어떤 node의 nearest neighbor에 거리가 1보다 작은 최근접 이웃이 있으면 True를, 모든 node의 NN에서 최근접 이웃까지의 거리가 1보다 크면 False를 반환한다.

$\phi$-평면 위 range query를 위한 자료구조를 구성하는 데 걸리는 시간은 $O(n \log^2 n)$, 자료구조의 크기는 $O(n \log n)$이다. range tree의 2단계 node가 $k$개의 subnode를 가진다고 하면, nearest neighbor 자료구조로 Voronoi diagram을 사용할 수 있다. 자료구조를 구성하는 데 걸리는 시간은 $O(k \log k)$, 자료구조의 크기는 $O(k)$이다. (Bottom-up construction으로 VD를 만들면 각 노드의 구성 시간을 $O(k)$ 안에 만들 수 있으나[4], 전체 시간복잡도는 query에 의해 dominate된다.) 종합하면 두 단계로 이루어진 자료구조를 만드는 데 걸리는 시간은 $O(n \log^3 n)$, 크기는 $O(n \log^2 n)$이 된다.

$\phi$-평면 위에서 range query는 $O(\log^2 n)$개의 tree node를 반환한다. 각각의 node마다 nearest query를 실행하는 데 걸리는 시간은 $O(\log k) \subseteq O(\log n)$이다. 두 원의 중심 거리를 계산하는 데 상수 시간이 소요되므로, 한 번의 query에 사용하는 시간은 $O(\log^3 n)$이다.

선분 $\overline{st}$를 기준으로 왼쪽에 $\ell$개, 오른쪽에 $r$개의 정점이 주어졌다고 가정하자. ($\ell + r = n$) 선분 오른쪽의 정점을 가지고 자료구조를 구성하면 $O(r \log^3 r)$ 시간이 소요된다. 선분 왼쪽 정점마다 최근접 이웃까지의 거리를 찾으면 $O(\ell \log^3 r)$만큼의 시간이 소요된다. 따라서, 두 집합 사이 $\overline{st}$를 지나는 간선이 있는지 확인하는 데 걸리는 전체 시간은 $O((\ell + r) \log^3 r) \approx O(n \log^3 n)$ 이다.

DG 위에서 segment-edge intersection 찾기

선분을 기준으로 왼쪽에 원 $a$, 오른쪽에 원들 ${b_1, b_2, \cdots, b_r}$이 있다고 가정하고, 원의 반지름을 각각 $r_a, r_{b_1}, r_{b_2}, \cdots, r_{b_r}$라고 하자. $| \overline{ab_i} | \le r_a + r_{b_i}$를 만족할 때 $a$와 $b_i$가 DG 간선으로 연결되어 있다. $r_a$가 고정되어 있으므로 원 $b_i$ 위에 $a$에 가장 가까운 점을 포함하는 $b_i$의 중심을 구하고, $a$의 중심으로부터 거리가 $r_a + r_{b_i}$ 미만임을 확인하는 것으로 문제를 해결할 수 있다. 따라서 UDG와 비슷한 방법으로 데이터 구조를 설계하되, 마지막 단계의 최근접 이웃을 구하는 데이터 구조를 변경한다.

오른쪽 원들 ${b_1, b_2, \cdots, b_r}$을 바탕으로 자료구조를 만든다. (거리에 상관없이)선분 $ab_i$가 $st$와 교차하는 조건은 UDG의 경우와 같다. 따라서 $b_i$의 중심들을 $\phi$-평면 위로 변환하여 range tree를 만든다.

range tree의 node마다 $a$를 받아 boundary까지의 거리가 가장 가까운 $b_i$를 반환하는 자료구조를 만들어야 한다. 이를 위해 Additively weighted Voronoi diagram([2], Section 4)의 자료구조를 이용한다. 이 자료구조는 각 점까지의 거리 + 점의 weight를 최소화하는 점으로 공간을 partition하며, Voronoi diagram을 구성하는 sweepline 기법을 약간 변형하여 구성한다. $k$개의 정점을 바탕으로 한 자료구조의 구성 시간은 여전히 $O(k \log k)$이며, 자료구조의 크기는 $O(k)$이다. Point location을 사용하여 최근접 이웃을 구할 수 있으며, 이 때에 걸리는 시간은 $O(\log k)$이다. 따라서 Cabello, Jejcic의 자료구조와 구성하는 시간, 크기, 그리고 입력 정점으로부터 가장 가까운 이웃 정점을 찾는 데 걸리는 query time이 모두 일치한다.

한편, 동일한 자료구조로 $a$와 ${b_1, b_2, \cdots, b_r}$ 사이의 간선 중 $st$와 겹치지 않는 간선이 존재하는지를 파악할 수도 있다. $\phi$-평면에서 오른쪽 아래의 점들만 쿼리하는 과정을 반대로 수행하면 충분하다. 나머지 2개의 사분면($\phi(a)$의 왼쪽 위에 $\phi(b)$가 놓일 수 없으므로)에 대한 range query를 수행하여 $st$와 겹치지 않는 점을 찾을 수 있다.

위의 내용을 종합하면 아래와 같이 정리할 수 있다.

Theorem. 평면 위 y축 오른쪽으로 $n$개의 정점 $B$가 주어져 있다. $B$의 정점을 $O(\log^3 n)$ 시간동안 처리하여, y축 왼쪽에 원 $a$가 들어올 때, $ab$와 $st$가 교차하면서 $|ab| \le r_a$인 $b \in B$가 존재하는지 $O(\log^3 n)$ 안에 판단하는 자료구조를 구성할 수 있다. 동일한 자료구조로 $ab$와 $st$가 교차하지 않으면서 $|ab| \le r_a$인 $b \in B$가 존재하는지 $O(\log^3 n)$ 안에 판단할 수 있다.

References

[1] Cabello, S., & Milinković, L. (2018). Two optimization problems for unit disks. Computational Geometry, 70, 1-12.

[2] Fortune, S. (1987). A sweepline algorithm for Voronoi diagrams. Algorithmica, 2(1), 153-174.

[3] Cabello, S., & Jejčič, M. (2015). Shortest paths in intersection graphs of unit disks. Computational Geometry, 48(4), 360-367.

[4] Shamos, M. I., & Hoey, D. (1975, October). Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) (pp. 151-162). IEEE.

[5] Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., & Sharir, M. (2020). Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. Discrete & Computational Geometry, 64(3), 838-904.

[6] Gibson, M., Kanade, G., & Varadarajan, K. (2011, September). On isolating points using disks. In European Symposium on Algorithms (pp. 61-69). Springer, Berlin, Heidelberg.

[7] Giannopoulos, P., Knauer, C., & Whitesides, S. (2008). Parameterized complexity of geometric problems. The Computer Journal, 51(3), 372-384.

[8] Intersection Graph from Wikipedia

[9] Unit Disk Graph from Wikipedia