Paper by Erik D. Demaine
- Ajay Deshpande, Taejung Kim, Erik D. Demaine, and Sanjay E. Sarma, “A Pseudopolynomial Time O(log n)-Approximation Algorithm for Art Gallery Problems”, in Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), Lecture Notes in Computer Science, volume 4619, Halifax, Nova Scotia, Canada, August 15–17, 2007, pages 163–174.
In this paper, we give a
O(log copt)-approximation algorithm for
the point guard problem where copt is the optimal
number of guards. Our algorithm runs in time polynomial in n, the
number of walls of the art gallery and the spread Δ, which is defined as
the ratio between the longest and shortest pairwise distances. Our algorithm
is pseudopolynomial in the sense that it is polynomial in the spread Δ
as opposed to polylogarithmic in the spread Δ, which could be
exponential in the number of bits required to represent the vertex positions.
The special subdivision procedure in our algorithm finds a finite set of
potential guard-locations such that the optimal solution to the art gallery
problem where guards are restricted to this set is at most
3 copt. We use a set cover cum VC-dimension
based algorithm to solve this restricted problem approximately.
- Unfortunately, the main result of this paper is flawed. In 2016, Édouard Bonnet and Tillman Miltzow showed that the goal of our Step 2 is in fact impossible, but that similar approaches lead to an approximation algorithm.
- The paper is 12 pages.
- The paper is available in PDF (151k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 13, 2020 by