论文标题
跨越树木的平面双重瓶颈
Planar Bichromatic Bottleneck Spanning Trees
论文作者
论文摘要
给定平面中的$ n $红色和蓝点的$ p $，$ p $的\ emph {planar bithotic spanning树}是$ p $的跨度树，因此每个边缘在红点和蓝点之间连接，没有两个边缘相交。在瓶颈平面双分散树问题中，目标是找到一个平面双跨度树$ t $，以便将$ t $中最长的边缘长度最小化。在本文中，我们表明此问题对于一般位置的积分是NP。此外，我们提出了一个多项式时$（8 \ sqrt {2}）$ - 近似算法，通过证明任何瓶颈$λ$的双分化生成树可以转换为最多$ 8 \ sqrt {2}λ$的瓶颈瓶颈的平面式跨度树。
Given a set $P$ of $n$ red and blue points in the plane, a \emph{planar bichromatic spanning tree} of $P$ is a spanning tree of $P$, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree $T$, such that the length of the longest edge in $T$ is minimized. In this paper, we show that this problem is NP-hard for points in general position. Moreover, we present a polynomial-time $(8\sqrt{2})$-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck $λ$ can be converted to a planar bichromatic spanning tree of bottleneck at most $8\sqrt{2}λ$.
