Skip to main navigation Skip to search Skip to main content

Floodlight illumination of infinite wedges

  • Matthew Cary
  • , Atri Rudra
  • , Ashish Sabharwal
  • , Erik Vee
  • Alphabet Inc.
  • Cornell University
  • Yahoo Research Labs

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 languageEnglish
Pages (from-to)23-34
Number of pages12
JournalComputational Geometry: Theory and Applications
Volume43
Issue number1
DOIs
StatePublished - 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