Minimum Two-point Separation in Geometric Intersection Graphs

Abstract

We study the minmum two-point separation problem on geometric intersection graphs: Given a set $\diskset$ of $n$ geometric objects in the plane and two points $s$ and $t$, find a smallest subset of $\diskset$ separating $s$ and $t$. Here, a subset of $\diskset$ separates $s$ and $t$ if any curve connecting $s$ and $t$ intersects the objects in the subset.

First, we present exact algorithms for unweighted and weighted unit disk graphs. A \emph{unit disk graph} $G = (V, E)$ is defined by a set $\diskset$ of unit disks in the plane. Each vertex of $V$ corresponds to a center of a disk of $\diskset$, and two vertices of $V$ are connected by an edge if their corresponding disks intersect. In a weighted unit disk graph, the weight of each edge is the Euclidean distance between the centers corresponding to the end vertices. For an unweighted unit disk graph, our algorithm runs in $O(n^2)$ time, which improves the previous algorithm that runs in $O(n^2 \log^3{n})$ [CGTA 2018]. For a weighted unit disk graph, we aim to minimize a total length of the edges in the induced subgraph by the subset of $\diskset$. In this case, we present an $O(n^2\log^2 n)$-time algorithm.

We newly propose two approximation algorithms which works for both unweighted and weighted unit disk graphs. The first algorithm uses a balanced graph separator for the unit disks. The running time of these algorithms are nearly $O(n^{1.5})$, and the size of the output is differ from the exact solution at most one. The second algorithm uses a planar spanner and runs in nearly $O(n)$, and the multiplicative approximation factor is bounded by the stretch of the spanner graph.

Finally, we propose minimum separation algorithms for non-unit disk graphs. The exact algorithm runs in $O(n^2 \log^3{n})$ time, which is a generalization of the previous algorithm for unit disks introduced by [CTGA 2018]. The approximation algorithm for a non-unit disk graph uses a spanner graph and its balanced separator. The running time of the algorithm is $O(n^{1.5})$, and the size of the output is bounded by $O(\log{\phi})$, where $\phi$ is the ratio between maximum and minimum radius of the disks.

본 논문에서는 기하 교차 그래프에서의 2점 최소 분리 집합 문제를 연구한다. 2점 최소 분리 집합 문제란, 평면 위 $n$개의 도형 $\diskset$와 두 개의 정점 $s$와 $t$가 주어져 있을 때 $s$와 $t$를 분리하는 $\diskset$의 최소 크기 부분집합을 찾는 문제이다. 여기서 $\diskset$의 부분집합이 $s$와 $t$를 분리한다는 것은, $s$와 $t$를 잇는 어떤 곡선도 그 부분집합의 도형 중 하나와 교차한다는 것을 의미한다.

본 논문에서는 (가중치 유무에 따라) 단위 원판 그래프 위의 최소 분리 집합을 정확하게 찾는 알고리즘을 소개한다.\textit{단위 원판 그래프}(unit disk graph) $G = (V, E)$는 평면 위 단위 원판의 집합 $\diskset$으로 정의된다. $V$에 해당하는 각 정점은 $\diskset$의 원판 중심과 대응되고, $V$의 두 정점은 대응하는 원판이 서로 교차할 때 간선으로 연결된다. 가중치를 갖는(weighted) 단위 원판 그래프에서 각 간선의 가중치는 두 정점에 해당하는 원판 중심 사이의 유클리드 거리이다. 본 논문은 가중치가 없는 단위 원판 그래프에서 $O(n^2)$ 시간에 실행되는 알고리즘을 제안하며, 이는 $O(n^2 \log^3{n}$ 시간에 실행하는 기존 알고리즘을 개선한다 [CGTA 2018]. 그래프가 가중치를 갖는 경우, 최소 분리 집합 문제는 $\diskset$의 부분집합으로 유도한 부분 그래프가 갖는 간선 길이의 합을 최소화하는 것을 목표로 한다. 본 논문에서는 가중치를 갖는 경우에 대한 $O(n^2 \log^2{n})$ 알고리즘을 제안한다.

본 논문에서는 또한 단위 원판 그래프 위의 분리 집합을 구하는 두 개의 근사 알고리즘을 새로 소개한다. 첫 번째 근사 알고리즘은 단위 원판 그래프의 균형잡힌 분리(balanced graph separator)를 사용한다. 이 알고리즘의 실행 시간은 거의 $O(n^{1.5})$이며, 알고리즘이 반환하는 답안과 최소 분리 집합의 크기 차이는 1 이하이다. 두 번째 알고리즘은 평면 스패너(planar spanner)를 사용하며, 거의 선형 시간에 실행된다. 이 알고리즘의 근사 비율은 사용한 스패너 그래프의 늘어난 정도(stretch)에 의해 결정된다.

마지막으로, 본 논문에서는 일반적인 원판 그래프에 대한 최소 분리 알고리즘을 제안한다. 본 논문에서는 [CGTA 2018]의 단위 원판에 대한 알고리즘을 일반화한 정확한 알고리즘을 제안하며, 실행 시간은 $O(n^2 \log^3{n})$이다. 원판 그래프에 대한 근사 알고리즘은 원판 그래프의 스패너 그래프와 균형잡힌 분리를 사용한다. 알고리즘의 실행시간은 $O(n^{1.5})$이고, 출력의 근사 비율은 $O(\log{\phi})$이며, 여기서 $\phi$는 원판들의 최대 반지름과 최소 반지름 사이의 비율을 의미한다.