Algorithms for art gallery illumination (Q2397430)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for art gallery illumination |
scientific article |
Statements
Algorithms for art gallery illumination (English)
0 references
22 May 2017
0 references
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.
0 references
art gallery problem
0 references
fading
0 references
computational geometry
0 references
linear program
0 references
nonlinear program
0 references
Lipschitz function
0 references
algorithm engineering
0 references
numerical examples
0 references
0 references