论文标题
$ \ frac {2π} {3} $ - mst的4- approximation
A 4-Approximation of the $\frac{2π}{3}$-MST
论文作者
论文摘要
首先在带有定向天线的无线网络的上下文中引入了有界角（最小）跨越树。他们让人联想到有限的跨越树木，这些树木受到了极大的关注。令$ p = \ {p_1，\ ldots，p_n \} $为飞机中的$ n $点集，令$π$为多边形路径$（p_1，\ ldots，p_n）$，让$ 0 <α<2π$是一个角度。 $α$ - 包裹的树（$α$ -ST）的$ P $是$ P $上完整的欧几里得图的跨越树，具有以下属性：对于P $中的每个顶点$ p_i \，（最小的）角度是所有边缘跨越$ p_i $的（最小的）角度，最多是$ p_i $。 $α$ - 最小生成树（$α$ -MST）是$α$ -S的最小重量的$α$ -ST，其中$α$ -ST的重量是其边缘长度的总和。在本文中，我们考虑了计算$α$ -MST的问题，对于$α= \ frac {2π} {3} $的重要情况。我们提出了一种简单的4个附属算法，从而改善了Aschner和Katz和Biniaz等人的先前结果，后者分别呈现了近似值6和$ \ frac {16} {3} $的算法。 为了获得此结果，我们设计了一种简单的$ o（n）$ - 时间算法，用于构建$ \ frac {2π} {3} $ - st \，$ {\ cal t} $ $ p $的$ p $，以至于$ {\ cal t} $的重量最大为$ usove $π$ and $π$和cal， $π$。从任何$ \ varepsilon> 0 $来说，都有一个多边形路径，后者的结果是最佳的，每个$ \ frac {2π} {3} $ - ST的权重大于$ 2- \ varepsilon $乘以路径的重量。
Bounded-angle (minimum) spanning trees were first introduced in the context of wireless networks with directional antennas. They are reminiscent of bounded-degree spanning trees, which have received significant attention. Let $P = \{p_1,\ldots,p_n\}$ be a set of $n$ points in the plane, let $Π$ be the polygonal path $(p_1,\ldots,p_n)$, and let $0 < α< 2π$ be an angle. An $α$-spanning tree ($α$-ST) of $P$ is a spanning tree of the complete Euclidean graph over $P$, with the following property: For each vertex $p_i \in P$, the (smallest) angle that is spanned by all the edges incident to $p_i$ is at most $α$. An $α$-minimum spanning tree ($α$-MST) is an $α$-ST of $P$ of minimum weight, where the weight of an $α$-ST is the sum of the lengths of its edges. In this paper, we consider the problem of computing an $α$-MST, for the important case where $α= \frac{2π}{3}$. We present a simple 4-approximation algorithm, thus improving upon the previous results of Aschner and Katz and Biniaz et al., who presented algorithms with approximation ratios 6 and $\frac{16}{3}$, respectively. In order to obtain this result, we devise a simple $O(n)$-time algorithm for constructing a $\frac{2π}{3}$-ST\, ${\cal T}$ of $P$, such that ${\cal T}$'s weight is at most twice that of $Π$ and, moreover, ${\cal T}$ is a 3-hop spanner of $Π$. This latter result is optimal in the sense that for any $\varepsilon > 0$ there exists a polygonal path for which every $\frac{2π}{3}$-ST has weight greater than $2-\varepsilon$ times the weight of the path.
