Abstract
The floodlight illumination problem asks whether there exists a one-to-one placement of n floodlights illuminating infinite wedges of angles α1,⋯, αn at n sites p1, ⋯, pn in a plane such that a given infinite wedge W of angle θ located at point q is completely illuminated by the floodlights. We prove that this problem is NP-hard, closing an open problem posed by Demaine and O'Rourke (CCCG 2001). In fact, we show that the problem is NP-complete even when αi=α for all 1≤i≤n (the uniform case) and θ=∑i=1n αi (the tight case).
| Original language | English |
|---|---|
| Pages (from-to) | 23-34 |
| Number of pages | 12 |
| Journal | Computational Geometry: Theory and Applications |
| Volume | 43 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 2010 |
Keywords
- Art gallery problem
- Floodlights
- Illumination
- NP-completeness
Fingerprint
Dive into the research topics of 'Floodlight illumination of infinite wedges'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver