{"ID":2824253,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.23297","arxiv_id":"2512.23297","title":"A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem","abstract":"Given a polygon $H$ in the plane, the art gallery problem calls for fining the smallest set of points in $H$ from which every other point in $H$ is seen. We give a deterministic algorithm that, given any polygon $H$ with $h$ holes, $n$ rational veritces of maximum bit-length $L$, and a parameter $δ\\in(0,1)$, is guaranteed to find a set of points in $H$ of size $O\\big(\\OPT\\cdot\\log(h+2)\\cdot\\log (\\OPT\\cdot\\log(h+2)))$ that sees at least a $(1-δ)$-fraction of the area of the polygon. The running time of the algorithm is polynomial in $h$, $n$, $L$ and $\\log(\\frac{1}δ)$, where $\\OPT$ is the size of an optimum solution.","short_abstract":"Given a polygon $H$ in the plane, the art gallery problem calls for fining the smallest set of points in $H$ from which every other point in $H$ is seen. We give a deterministic algorithm that, given any polygon $H$ with $h$ holes, $n$ rational veritces of maximum bit-length $L$, and a parameter $δ\\in(0,1)$, is guarant...","url_abs":"https://arxiv.org/abs/2512.23297","url_pdf":"https://arxiv.org/pdf/2512.23297v2","authors":"[\"Khaled Elbassioni\"]","published":"2025-12-29T08:36:04Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}