Algorithms for art gallery illumination

DOI10.1007/S10898-016-0452-2zbMATH Open1367.65028DBLPjournals/jgo/ErnestusFHKKMS17arXiv1410.5952OpenAlexW1889620494WikidataQ59529122 ScholiaQ59529122MaRDI QIDQ2397430FDOQ2397430

Christiane Schmidt, Michael Hemmer, Alexander Kröller, Maximilian Ernestus, Jan Kokemüller, Stephan Friedrichs, Mahdi Moeini

Publication date: 22 May 2017

Published in: Journal of Global Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1410.5952

Recommendations

• An exact algorithm for minimizing vertex guards on art galleries
• Exact solutions and bounds for general art gallery problems
• scientific article; zbMATH DE number 1424310
• Facets for art gallery problems
• Exact Solutions and Bounds for General Art Gallery Problems

zbMATH Keywords

numerical examplescomputational geometryLipschitz functionalgorithm engineeringlinear programart gallery problemnonlinear programfading

Mathematics Subject Classification ID

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

Cites Work

• Algorithm 966
• Global optimization in action. Continuous and Lipschitz optimization: algorithms, implementations and applications
• A short proof of Chvatal's Watchman Theorem
• Traditional Galleries Require Fewer Watchmen
• An exact algorithm for minimizing vertex guards on art galleries
• A combinatorial theorem in plane geometry
• The computational geometry algorithms library CGAL
• Exact solutions and bounds for general art gallery problems
• A Novel Efficient Approach for Solving the Art Gallery Problem
• Inapproximability results for guarding polygons and terrains
• Computational complexity of art gallery problems
• Facets for art gallery problems
• Art gallery problem with guards whose range of vision is \(180^{\circ}\)
• ENERGY-AWARE STAGE ILLUMINATION

Cited In (2)

• On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
• Solving the Illumination Problem with Heuristics

Uses Software

• CGAL
• Global Optimization Toolbox For Maple
• CPLEX

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)