Kunst! - Exact Algorithms for Art Gallery Variants

(DFG Priority Program 1307: Algorithm Engineering)

The classical Art Gallery Problem (AGP) asks for the minimum number of guards that achieve visibility coverage of a given polygon. This problem is known to be NP-hard, even for very restricted and discrete special cases. For the general problem (in which both the set of possible guard positions and the point set to be guarded are uncountable), neither constant-factor approximation algorithms nor exact solution methods are known. We develop a primal-dual approach for general art gallery problems in arbitrary polygons with holes, in which guards can be placed anywhere, such that the entire interior of the polygon is guarded. Our method computes a sequence of lower and upper bounds on the optimal number of guards until-in case of convergence and integrality-eventually an optimal solution is reached. Our algorithm is based on a formulation of the problem as a (covering) linear program. It solves the problem using a cutting plane and column generation approach, i.e., by solving the primal and dual separation problems. Computational results show the usefulness of our method.

In the project "Kunst!", we are interested in investigating different aspects of AGP, for example:

News

Our software that implements the LP-based procedure described in [1] will soon be released here under the GNU General Public License.

Theses

Project members

Publications

[1] T. Baumgartner, S. Fekete, A. Kröller, C. Schmidt:
Exact Solutions and Bounds for General Art Gallery Problems,
In the Proceedings of the 2010 Workshop on Algorithm Engineering and Experiments (ALENEX10), Austin, USA, 2010, pp.11-22.
PDF ,

Further Information

For further information, contact the project members.