Algorithms for art gallery illumination

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical mathematical programming methods (65K05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40) Linear programming (90C05) Nonlinear programming (90C30) Applications of mathematical programming (90C90)

Abstract: 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.

Review text

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.

Recommendations

Cites work

Cited in

(5)

Describes a project that uses

Uses Software

This page was built for publication: Algorithms for art gallery illumination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397430)