Exact Solutions and Bounds for General Art Gallery Problems

The Twelfth Workshop on Algorithm Engineering and Experiments

Tobias Baumgartnery S

Others  :  http://www.siam.org/proceedings/alenex/2010/alx10_002_baumgartnert.pdf
PID  :  38127

来源: CEUR

【 摘 要 】

The classical Art Gallery Problem asks for the mini- mum 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 case of vertex guards and simple orthogonal polygons, Cuoto et al. have recently developed an exact method that is based on a set cover approach. 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 present a primal-dual algorithm based on linear programming that provides lower bounds on the necessary number of guards in every step and|in case of convergence and integrality|ends with an optimal solution. We describe our implementation and give results for an assortment of polygons, including non-orthogonal polygons with holes.