Illumination by floodlights

William Steiger, Ileana Streinu

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

We consider three problems about the illumination of planar regions with floodlights of prescribed angles. Problem 1 is the decision problem: given a wedge W of angle φ ≤ π, n points p1 . . . . . pn in the plane and n angles α1 . . . . . αn such that ∑ni=1 αi ≤ θ, decide whether W can be illuminated by floodlights of angles α1 , . . . , αn placed in some order at the points p1 , . . . , pn and then rotated appropriately. We show that this problem is the exponential time and a specialized version of it (when φ = θ) is in NP. The second problem arises when the n points are in the complementary wedge of W and θ ≥ φ. Boss et al. have shown that a solution exists and gave an O(n log n) algorithm to place the floodlights. Here we give a matching lower bound. Problem 3 involves the illumination of the whole plane. The algorithm of Bose et al. uses an O(n log n) tripartitioning algorithm to reduce problem 3 to problem 2. We give a linear time tripartitioning algorithm of independent interest.

Original languageEnglish (US)
Pages (from-to)57-70
Number of pages14
JournalComputational Geometry: Theory and Applications
Volume10
Issue number1
DOIs
StatePublished - Jan 1 1998

Fingerprint

Illumination
Lighting
Angle
Wedge
Exponential time
Linear-time Algorithm
Decision problem
Lower bound

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this

Steiger, William ; Streinu, Ileana. / Illumination by floodlights. In: Computational Geometry: Theory and Applications. 1998 ; Vol. 10, No. 1. pp. 57-70.
@article{5f528940f9eb45febdb89b29798e3599,
title = "Illumination by floodlights",
abstract = "We consider three problems about the illumination of planar regions with floodlights of prescribed angles. Problem 1 is the decision problem: given a wedge W of angle φ ≤ π, n points p1 . . . . . pn in the plane and n angles α1 . . . . . αn such that ∑ni=1 αi ≤ θ, decide whether W can be illuminated by floodlights of angles α1 , . . . , αn placed in some order at the points p1 , . . . , pn and then rotated appropriately. We show that this problem is the exponential time and a specialized version of it (when φ = θ) is in NP. The second problem arises when the n points are in the complementary wedge of W and θ ≥ φ. Boss et al. have shown that a solution exists and gave an O(n log n) algorithm to place the floodlights. Here we give a matching lower bound. Problem 3 involves the illumination of the whole plane. The algorithm of Bose et al. uses an O(n log n) tripartitioning algorithm to reduce problem 3 to problem 2. We give a linear time tripartitioning algorithm of independent interest.",
author = "William Steiger and Ileana Streinu",
year = "1998",
month = "1",
day = "1",
doi = "10.1016/S0925-7721(97)00027-8",
language = "English (US)",
volume = "10",
pages = "57--70",
journal = "Computational Geometry: Theory and Applications",
issn = "0925-7721",
publisher = "Elsevier",
number = "1",

}

Illumination by floodlights. / Steiger, William; Streinu, Ileana.

In: Computational Geometry: Theory and Applications, Vol. 10, No. 1, 01.01.1998, p. 57-70.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Illumination by floodlights

AU - Steiger, William

AU - Streinu, Ileana

PY - 1998/1/1

Y1 - 1998/1/1

N2 - We consider three problems about the illumination of planar regions with floodlights of prescribed angles. Problem 1 is the decision problem: given a wedge W of angle φ ≤ π, n points p1 . . . . . pn in the plane and n angles α1 . . . . . αn such that ∑ni=1 αi ≤ θ, decide whether W can be illuminated by floodlights of angles α1 , . . . , αn placed in some order at the points p1 , . . . , pn and then rotated appropriately. We show that this problem is the exponential time and a specialized version of it (when φ = θ) is in NP. The second problem arises when the n points are in the complementary wedge of W and θ ≥ φ. Boss et al. have shown that a solution exists and gave an O(n log n) algorithm to place the floodlights. Here we give a matching lower bound. Problem 3 involves the illumination of the whole plane. The algorithm of Bose et al. uses an O(n log n) tripartitioning algorithm to reduce problem 3 to problem 2. We give a linear time tripartitioning algorithm of independent interest.

AB - We consider three problems about the illumination of planar regions with floodlights of prescribed angles. Problem 1 is the decision problem: given a wedge W of angle φ ≤ π, n points p1 . . . . . pn in the plane and n angles α1 . . . . . αn such that ∑ni=1 αi ≤ θ, decide whether W can be illuminated by floodlights of angles α1 , . . . , αn placed in some order at the points p1 , . . . , pn and then rotated appropriately. We show that this problem is the exponential time and a specialized version of it (when φ = θ) is in NP. The second problem arises when the n points are in the complementary wedge of W and θ ≥ φ. Boss et al. have shown that a solution exists and gave an O(n log n) algorithm to place the floodlights. Here we give a matching lower bound. Problem 3 involves the illumination of the whole plane. The algorithm of Bose et al. uses an O(n log n) tripartitioning algorithm to reduce problem 3 to problem 2. We give a linear time tripartitioning algorithm of independent interest.

UR - http://www.scopus.com/inward/record.url?scp=0041125889&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041125889&partnerID=8YFLogxK

U2 - 10.1016/S0925-7721(97)00027-8

DO - 10.1016/S0925-7721(97)00027-8

M3 - Article

AN - SCOPUS:0041125889

VL - 10

SP - 57

EP - 70

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

IS - 1

ER -