  The Art Gallery Problem (AGP) is one of the classical problems in
computational geometry. It asks for the minimum number of guards required to
achieve visibility coverage of a given polygon. The AGP is well-known to be
NP-hard even in restricted cases. In this paper, we consider the Art Gallery
Problem with Fading (AGPF): A polygonal region is to be illuminated with light
sources such that every point is illuminated with at least a global threshold,
light intensity decreases over distance, and we seek to minimize the total
energy consumption. Choosing fading exponents of zero, one, and two are
equivalent to the AGP, laser scanner applications, and natural light,
respectively. We present complexity results as well as a negative solvability
result. Still, we propose two practical algorithms for AGPF with fixed light
positions (e.g. vertex guards) independent of the fading exponent, which we
demonstrate to work well in practice. One is based on a discrete approximation,
the other on non-linear programming by means of simplex-partitioning
strategies. The former approach yields a fully polynomial-time approximation
scheme for AGPF with fixed light positions. The latter approach obtains better
results in our experimental evaluation.
