Floodlight Illumination Problems

Table of contents

• The stage illumination problem
• Illuminating polygons with vertex pi-floodlights
• Illuminating polygons with point pi-floodlights
• Illuminating polygons with vertex floodlights
• Optimal floodlight illumination of polygons

Floodlight Illumination problems

Given an angle $$a we define an $$a-floodlight to be a light source $$f located at a point $$p of the plane that emits light within an angular region of size at most $$a. The point $$p is called the apex of $$f. If the apex of $$f is located at a vertex of a polygon, $$f is called a vertex floodlight, otherwise we call it a point floodlight. If $$a=180, $$f is called a pi-floodlight

The stage illumination problem

The following problem was posed by Urrutia in 1992.

Stage Illumination problem: Find, if possible, an efficient algorithm to solve the following problem: Let L be a line segment contained in the x-axis of the plane, and $$F={ f₁, ... , f_n } be a set of floodlights with sizes $${ a₁, ... , a_n} resp. such that their apexes are located at some fixed points on the plane, all on the same side of L. Is it possible to rotate the floodlights around their apexes so as to obtain a final configuration such that L is completely illuminated?

Illuminating polygons with vertex pi-floodlights

The following conjecture is due to Urrutia:

Conjecture Floor[(3n)/5]+c vertex pi-floodlights are always sufficient to illuminate any polygon with n vertices, c a constant.

F. Santos has produced a family of polygons that achieve this bound. They are produced by "pasting" copies of the polygon at the left of the next figure. At the moment, we do not even have a proof that there is a constant b < 0 such that b n vertex pi-floodlights are sufficient to illuminate any polygon with n vertices.

Illuminating polygons with point pi-floodlights

For pi-floodlights located anywhere within a polygon, the following conjecture, to my knowledge posed independently by J. Pach, Czismadia and Toth , and Urrutia, is open:

Conjecture n/3 + c pi-floodlights are always sufficient to illuminate any polygon with n vertices.

The best upper bound known to date is due to Czismadia and Toth. They proved that Floor[2(n-3)/5] pi-floodlights always suffice.

Illuminating polygons with vertex floodlights

Consider three angles $$a₁, $$a₂, $$a₃ such that:

$$a₁ + $$a₂ + $$a₃ = pi.

Urrutia proved that any convex polygon $$P_n with n vertices can always be illuminated with three vertex floodlights $$f₁, $$f₂, and $$f_i of sizes $$a₁, $$a₂, and $$a_i respectively.

O'Rourke, Shermer, and Streinu proved that Urrutia's result does not hold for m angles $$a₁,..., $$a_m such that $$a₁+...+ $$a_m = pi; m large enough. In their proof m is greater than 1000. O'Rourke, Shermer and Streinu posed the following problem:

Problem: Find the smallest m for which there are m angles $$a₁+...+ $$a_m= pi, such that there is a polygon with at least m vertices that cannot be illuminated with m vertex floodlights $$f₁,..., $$f_m of sizes at most $$a₁,.... $$a_m respectively.

Even the case of four pi/4- or five pi/5-floodlights remains open! I still hope that m > 4 .

A problem arising from O'Rourke, Sheremer and Streinu is this:

Problem: Find the smallest angle a such that any set of m floodlights of sizes $$a₁,.... $$a_m that add up to a are always sufficient to illuminate any convex polygon with at least m vertices.

It is known that 2pi suffices; this follows from a result of Bose, Guibas, Lubiw, Overmars, Souvaine and Urrutia.

Optimal floodlight illumination of polygons

Consider a set $$S={f₁,..., $$f_m} of m floodlights of sizes $$a₁,.... $$a_m. The size of $$S is defined to be $$a₁+....+ $$a_m. A set S of m floodlights that illuminates a polygon P is called m-optimal, if the size of S is minimal over all sets of m floodlights that illuminate P. V. Estivill-Castro and J. Urrutia obtained an $$O(n²) time algorithm to find a 2-optimal floodlight set for convex polygons with n vertices.

Problem: Find if possible, a subquadratic algorithm to solve the optimal 2-floodlight illumination problem for convex polygons.

The following problems are due to V. Estivill-Castro and J. Urrutia:

Problem: Is it true that for any k, the apexes of an optimal set of k-floodlights that illuminate a convex polygon P lie on vertices of P?

This result is true for k=2, and open for k>2.

Back to the main open problems page. Back to my home page.