The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS
The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS
复制标题
连续1.5D地形防护问题：离散化、最优解和PTAS
DOI：
--
复制
发表时间：
2015
影响因子：
0.3
通讯作者：
Christiane Schmidt
中科院分区：
文献类型：
--
作者：
Stephan Friedrichs;M. Hemmer;James A. King;Christiane Schmidt
在NP-困难的连续1.5维地形防护问题（TGP）中，我们给出了一个$R ^2 $（地形$T$）中的$x$-单调线段链，并要求保护所有$T$所需的最小数量的保护（位于$T$上的任何位置）。我们构造多项式大小的保护候选集和见证集$G，W \子集T$，使得对于$W$的任何可行（最优）保护覆盖$G^* \子集G$对于连续TGP也是可行（最优）的。（2）利用吉布森等人的多项式时间近似方法（PTAS），给出了一个连续TGP的PTAS; (3)将连续三峡工程规划问题表示为一个线性规划问题。此外，我们提出了几种过滤技术，减少我们的离散化的大小，使我们能够设计一个有效的基于IP的算法，可靠地提供最佳的后卫位置的地形高达10^6 $顶点在几分钟内在一个标准的台式计算机上。
In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an $x$-monotone chain of line segments in $R^2$ (the terrain $T$), and ask for the minimum number of guards (located anywhere on $T$) required to guard all of $T$. We construct guard candidate and witness sets $G, W \subset T$ of polynomial size such that any feasible (optimal) guard cover $G^* \subseteq G$ for $W$ is also feasible (optimal) for the continuous TGP. This discretization allows us to: (1) settle NP-completeness for the continuous TGP; (2) provide a Polynomial Time Approximation Scheme (PTAS) for the continuous TGP using the PTAS for the discrete TGP by Gibson et al.; (3) formulate the continuous TGP as an Integer Linear Program (IP). Furthermore, we propose several filtering techniques reducing the size of our discretization, allowing us to devise an efficient IP-based algorithm that reliably provides optimal guard placements for terrains with up to $10^6$ vertices within minutes on a standard desktop computer.
美术馆问题的各个方面
影响因子：
1.1
作者：
Sándor P. Fekete;Stephan Friedrichs;Alexander Kröller;Christiane Schmidt
通讯作者：
Christiane Schmidt