@inproceedings{4b9bfcafd126481984c97279eea9fbcf,
title = "An Approximation Algorithm for the Art Gallery Problem",
abstract = "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.",
author = "{\'E}douard Bonnet and Till Miltzow",
year = "2017",
doi = "10.4230/LIPIcs.SoCG.2017.20",
language = "English",
series = "LIPIcs",
publisher = "Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik GmbH",
pages = "20:1--20:15",
editor = "Boris Aronov and Katz, {Matthew J.}",
booktitle = "33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia",
}