Given an angle we define an -floodlight to be a light source located at a point of the plane that emits light within an angular region of size at most . The point is called the apex of . If the apex of is located at a vertex of a polygon, is called a vertex floodlight, otherwise we call it a point floodlight. If =180, is called a pi-floodlight
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 be a set of floodlights with sizes 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?
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.
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.
Consider three angles , , such that:
+ + = pi.
Urrutia proved that any convex polygon with n vertices can always be illuminated with three vertex floodlights , , and of sizes , , and respectively.
O'Rourke, Shermer, and Streinu proved that Urrutia's result does not hold for m angles ,..., such that +...+ = 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 +...+ = pi, such that there is a polygon with at least m vertices that cannot be illuminated with m vertex floodlights ,..., of sizes at most ,.... 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 ,.... 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.
Consider a set ,..., of m floodlights of sizes ,.... . The size of is defined to be +....+ . 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 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.
Jorge Urrutia, Department of Computer Science, University of Ottawa,