论文标题
为美术馆问题实施多边形守卫算法
Implementation of polygon guarding algorithms for art gallery problems
论文作者
论文摘要
维克多·克莱（Victor Klee）在1976年8月在斯坦福大学举行的一次会议上介绍了美术馆问题：“需要多少名警卫来保护美术馆？” 1987年，Ghosh为顶点守卫问题提供了一种近似算法，该算法达到了$ O（\ log n）$近似值。在2017年，Bhattacharya等。 Al提出了一种近似算法，用于保护弱的可见性多边形。在我们的论文中，我们首先实施这些算法，然后对它们进行不同类型的多边形测试。我们根据他们使用的后卫数量进行比较。在最后一部分中，我们提供了一种使用Ghosh的想法的新算法。实验表明，该算法分配了守卫输入多边形的最佳守卫。
Victor Klee introduce the art gallery problem during a conference in Stanford in August 1976 with that question: "How many guards are required to guard an art gallery?" In 1987, Ghosh provided an approximation algorithm for vertex guards problem that achieved $ O(\log n) $ approximation ratio. In 2017, Bhattacharya et. al presented an approximation algorithm for guarding weak visibility polygons. In our paper, we first implement these algorithms and then we test them for different types of polygons. We compare their performance in terms of number of guards used by them. In the last part, we have provided a new algorithm that uses Ghosh's idea. Experiments show that this algorithm assigns near optimal guards for guarding the input polygons.
