A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
复制标题
一种用于保护 1.5 维地形的 4 近似算法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
James A. King
中科院分区：
文献类型：
--
作者：
James A. King
在1.5维地形保护问题中，我们被给出一个x-单调链(地形)作为输入，并要求得到最小保护集(地形上的点)，使得地形上的每个点至少被一个保护所看到。最近的研究表明，1.5维地形守卫问题可以在一个恒定因子内逼近[3，7]，尽管没有人试图使逼近因子最小化。对于二次时间内的1.5维地形守卫问题，我们给出了一个4-近似算法。我们的算法比以前的算法更快、更简单，并且具有更好的最坏情况逼近因子。
In the 1.5-dimensional terrain guarding problem we are given as input an x-monotone chain (the terrain) and asked for the minimum set of guards (points on the terrain) such that every point on the terrain is seen by at least one guard. It has recently been shown that the 1.5-dimensional terrain guarding problem is approximable to within a constant factor [3,7], though no attempt has been made to minimize the approximation factor. We give a 4-approximation algorithm for the 1.5D terrain guarding problem that runs in quadratic time. Our algorithm is faster, simpler, and has a better worst-case approximation factor than previous algorithms.