论文标题
几何相交图中的最小切割
Minimum Cuts in Geometric Intersection Graphs
论文作者
论文摘要
令$ \ mathcal {d} $为飞机上的$ n $磁盘。对于$ \ mathcal {d} $，磁盘图$ g_ \ mathcal {d} $是带有顶点set $ \ mathcal {d} $的无向图，其中两个磁盘在相交时仅在且仅在它们相交时由边缘连接。定向传输图$ g^{\ rightarrow} _ \ Mathcal {d} $ for $ \ nathcal {d} $是带有顶点套装$ \ MATHCAL {D} $的有向图 if $D_1$ contains the center of $D_2$. 给定$ \ MATHCAL {D} $和两个非交流磁盘$ s，t \ in \ Mathcal {d} $，我们表明，最低$ s $ -s $ -t $ t $ tugtex以$ g_ \ g_ \ mathcal {d} $或$ g^{\ rightArrow} _ \ rightarrow} _ \ Mathcal Cos in $ G_ \ Mathcal {d} $ coin $ o（n^{3/2} \ text {polylog} n）$预期时间。为了获得我们的结果，我们将一般图中最大流量问题的算法与动态几何数据结构结合在一起，以操纵磁盘。 作为应用程序，我们考虑矩形域中的屏障弹性问题。在此问题中，我们有一个垂直条款$ s $，由两条垂直线，$ l_ \ ell $和$ l_r $以及一个集合$ \ MATHCAL {D} $的集合。让$ a $是$ s $的点，而不是$ \ mathcal {d} $的所有磁盘，然后让$ s $ s $ s $的$ b $以下$ \ mathcal {d} $下方。任务是找到一个从$ a $ a $ a $的曲线，该曲线位于$ s $中，并且与$ \ Mathcal {d} $的圆盘相交。使用我们改进的算法在磁盘图中最小切割，我们可以在$ O（n^{3/2} \ text {polylog} n）$预期时间中解决屏障弹性问题。
Let $\mathcal{D}$ be a set of $n$ disks in the plane. The disk graph $G_\mathcal{D}$ for $\mathcal{D}$ is the undirected graph with vertex set $\mathcal{D}$ in which two disks are joined by an edge if and only if they intersect. The directed transmission graph $G^{\rightarrow}_\mathcal{D}$ for $\mathcal{D}$ is the directed graph with vertex set $\mathcal{D}$ in which there is an edge from a disk $D_1 \in \mathcal{D}$ to a disk $D_2 \in \mathcal{D}$ if and only if $D_1$ contains the center of $D_2$. Given $\mathcal{D}$ and two non-intersecting disks $s, t \in \mathcal{D}$, we show that a minimum $s$-$t$ vertex cut in $G_\mathcal{D}$ or in $G^{\rightarrow}_\mathcal{D}$ can be found in $O(n^{3/2}\text{polylog} n)$ expected time. To obtain our result, we combine an algorithm for the maximum flow problem in general graphs with dynamic geometric data structures to manipulate the disks. As an application, we consider the barrier resilience problem in a rectangular domain. In this problem, we have a vertical strip $S$ bounded by two vertical lines, $L_\ell$ and $L_r$, and a collection $\mathcal{D}$ of disks. Let $a$ be a point in $S$ above all disks of $\mathcal{D}$, and let $b$ a point in $S$ below all disks of $\mathcal{D}$. The task is to find a curve from $a$ to $b$ that lies in $S$ and that intersects as few disks of $\mathcal{D}$ as possible. Using our improved algorithm for minimum cuts in disk graphs, we can solve the barrier resilience problem in $O(n^{3/2}\text{polylog} n)$ expected time.
