Algorithms for Art Gallery Illumination

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

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

Algorithms for Art Gallery Illumination

MPS-Authors

/persons/resource/persons135692

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

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:1410.5952.pdf
(プレプリント), 753KB

付随資料 (公開)

There is no public supplementary material available

引用

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

引用: https://hdl.handle.net/11858/00-001M-0000-0024-43BC-B

要旨

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.