Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms for art gallery illumination
TU Braunschweig, Germany.
Max Planck Institute Informat, Germany; Saarbrucken Grad School Comp Science, Germany.
TU Braunschweig, Germany.
TU Braunschweig, Germany.
Show others and affiliations
2017 (English)In: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 68, no 1, p. 23-45Article in journal (Refereed) Published
Abstract [en]

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 AGP 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 the AGPF with fixed light positions. The latter approach obtains better results in our experimental evaluation.

Place, publisher, year, edition, pages
SPRINGER , 2017. Vol. 68, no 1, p. 23-45
Keywords [en]
Art gallery problem; Fading; Computational geometry; Linear program; Non-linear program; Lipschitz function; Algorithm engineering
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-137382DOI: 10.1007/s10898-016-0452-2ISI: 000399244900002OAI: oai:DiVA.org:liu-137382DiVA, id: diva2:1096697
Note

Funding Agencies|Max Planck Society; Deutsche Forschungsgemeinschaft (DFG) [KR 3133/1-1]; CNRS; OSEO within the ISI project "Pajero" (France); Swedens innovation agency VINNOVA [2014-03476]; Israeli Centers of Research Excellence (I-CORE) program [4/11]

Available from: 2017-05-18 Created: 2017-05-18 Last updated: 2017-06-14

Open Access in DiVA

fulltext(1182 kB)77 downloads
File information
File name FULLTEXT01.pdfFile size 1182 kBChecksum SHA-512
8a8ddacef06f5d6bfa46c1ebc613478e5984f0c9a1e75df4f4c9134e7f0bd47325c8776b4a6dc803539a110fe631fcc9a66a3b288b67aca7ab08ea983862a3ce
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Schmidt, Christiane
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
Journal of Global Optimization
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 77 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 172 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf