Algorithms for art gallery illumination

DOI10.1007/S10898-016-0452-2MaRDI QIDQ2397430zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 22 May 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(4)

• Energy-aware stage illumination
• On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
• Constrained light deployment for reducing energy consumption in buildings
• Solving the Illumination Problem with Heuristics

Describes a project that uses

Uses Software

• CPLEX
• Global Optimization Toolbox For Maple
• CGAL

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)