An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem
An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem
复制标题
正交美术馆问题的精确高效算法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
P. J. Rezende
中科院分区：
文献类型：
--
作者：
Marcelo C. Couto;C. C. Souza;P. J. Rezende
在本文中，我们提出了一个精确的算法来解决正交画廊问题，其中警卫只能放置在多边形P的顶点代表画廊。我们的方法是基于离散化的P到一组有限的点在其内部。该算法反复求解集合覆盖问题的一个实例，获得P的顶点的最小集合Z，该最小集合Z可以查看当前离散化中的所有点。当P从Z完全可见时，算法停止;否则，离散化被细化并进行另一次迭代。我们建立的算法总是收敛到一个最佳的解决方案，提出了一个最坏的情况下分析的迭代次数，可能会受到影响。即使这些理论上可以达到0（n4），我们的计算实验表明，在实践中，它们在n中是线性的，并且对于n ≤ 200，它们实际上在几乎所有情况下都保持小于3。此外，与可能的O（n4）个原子可见性多边形相比，初始离散化中的点的数量较低，0（n2），使得总执行时间短得多。最佳的解决方案，为不同类别的多边形的实例与多达200个顶点也进行了说明。
In this paper, we propose an exact algorithm to solve the orthogonal art gallery problem in which guards can only be placed on the vertices of the polygon P representing the gallery. Our approach is based on a discretization of P into a finite set of points in its interior. The algorithm repeatedly solves an instance of the set cover problem obtaining a minimum set Z of vertices of P that can view all points in the current discretization. Whenever P is completely visible from Z, the algorithm halts; otherwise, the discretization is refined and another iteration takes place. We establish that the algorithm always converges to an optimal solution by presenting a worst case analysis of the number of iterations that could be effected. Even though these could theoretically reach 0(n4), our computational experiments reveal that, in practice, they are linear in n and, for n les 200, they actually remain less than three in almost all instances. Furthermore, the low number of points in the initial discretization, 0(n2), compared to the possible O(n4) atomic visibility polygons, renders much shorter total execution times. Optimal solutions found for different classes of instances of polygons with up to 200 vertices are also described.