Algorithms for art gallery illumination (Q2397430)

The original art gallery problem (AGP) is to find the position of a minimal number of guards such that they can supervise all places in a polygonal gallery. If the guards are replaced by light sources, then the problem is to illuminate all places above some threshold, given that light is fading with the distance like \(d^{-\alpha}\), this becomes the AGP with fading (AGPF) in which the total amount of energy sent out is to be minimized given a finite set of light sources. This paper concentrates on the vertex guard problem variant (the guards are placed at a fixed set of positions) and gives only a short introduction to the general point guard problem (guards can be anywhere in the gallery). The problem is NP-hard and not solvable unless the fading is topped to a constant near the light source. Two algorithms are given: a discrete version approximating the fading by a step function (it is a fully polynomial time approximation scheme) and a continuous version that relies on a global optimization scheme using a simplex partitioning to identify the darkest point. The algorithms are illustrated numerically with several examples.