English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Algorithms for Art Gallery Illumination

MPS-Authors
/persons/resource/persons135692

Friedrichs,  Stephan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1410.5952.pdf
(Preprint), 753KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Ernestus, M., Friedrichs, S., Hemmer, M., Kokemüller, J., Kröller, A., Moeini, M., et al. (2014). Algorithms for Art Gallery Illumination. Retrieved from http://arxiv.org/abs/1410.5952.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-43BC-B
Abstract
We consider a variant of the Art Gallery Problem, where a polygonal region is to be covered with light sources, with light fading over distance. We describe two practical algorithms, one based on a discrete approximation, and another based on nonlinear programming by means of simplex partitioning strategies. For the case where the light positions are given, we describe a fully polynomial-time approximation scheme. For both algorithms we present an experimental evaluation.