2026-08-10T23:31:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7215 2024-03-06T10:39:58Z ddc:004 open_access

An Approximation Algorithm for the Art Gallery Problem Bonnet, Édouard Miltzow, Tillmann computational geometry art gallery approximation algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Tillmann Miltzow 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.20 urn:nbn:de:0030-drops-72150 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.20 eng https://creativecommons.org/licenses/by/3.0/legalcode