文章基本信息

标题：An Approximation Algorithm for the Art Gallery Problem
本地全文：下载
作者：E}douard Bonnet ; Tillmann Miltzow
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：77
页码：20:1-20:15
DOI：10.4230/LIPIcs.SoCG.2017.20
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given a simple polygon P on n vertices, two points x, y in P are said to be visible to each other if the line segment between x and y is contained in P. The Point Guard Art Gallery problem asks for a minimum-size set S such that every point in P is visible from a point in S. The set S is referred to as guards. Assuming integer coordinates and a specific general position on the vertices of P, we present the first O(log OPT)-approximation algorithm for the point guard problem. This algorithm combines ideas in papers of Efrat and Har-Peled and Deshpande et al. We also point out a mistake in the latter.
关键词：computational geometry; art gallery; approximation algorithm