Improved Approximation for Guarding Simple Galleries from the Perimeter
Improved Approximation for Guarding Simple Galleries from the Perimeter
复制标题
改进了从外围保护简单画廊的近似方法
DOI：
--
复制
发表时间：
2010
影响因子：
0.8
通讯作者：
D. Kirkpatrick
中科院分区：
文献类型：
--
作者：
James A. King;D. Kirkpatrick
我们提供了一个O（log log opt）-近似算法的问题，守卫一个简单的多边形与警卫的周长。首先，我们设计了一个多项式时间算法，用于为与我们的保护问题相关的命中集的实例构建大小为O（\frac{1}{\varepad}\log\log\frac{1}{\varepad}）$的ε-网。然后，我们应用Brönnimann和古德里奇的技术，建立一个近似算法，从这个ε-网络发现。沿着一个简单的多边形P，我们的算法作为输入的一个有限的一组潜在的保护位置，必须包括多边形的顶点。如果未指定潜在保护位置的有限集合，例如，当警卫可以被放置在周界上的任何地方时，我们使用已知的离散化技术，代价是使算法的运行时间在顶点之间的最长距离和最短距离之间的比率中潜在地呈线性。我们的算法是第一个改进O（日志选择）-近似算法，使用通用的网络查找有限VC维集系统。
We provide an O(log log opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size $O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})$ for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.