page 1  (18 pages) 2

THE FLOODLIGHT PROBLEM?

Prosenjit Bose1 Leonidas Guibas2 Anna Lubiw3

Mark Overmars4 Diane Souvaine5 Jorge Urrutia6

Abstract
Given three angles summing to 2ss , given n points in the plane and a tripartition k1 + k2 + k3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge contains ki of the points. This new result on dissecting point sets is used to prove that lights of specified angles not exceeding ss can be placed at n fixed points in the plane to illuminate the entire plane if and only if the angles sum to at least 2ss . We give O(n log n) algorithms for both these problems.

1. Introduction

Illumination problems have been a source of many interesting results in computational geometry, for example in the area of Art Gallery theorems and algorithms|see [O'R], [S]. The usual scenario is that we have some target objects in two or more dimensions that are to be illuminated, and some specified sites for lights, which are assumed to shine light in every direction|i.e. with an angle of illumination of 360ffi in the planar case. See [CRU] and [CRCU] for some recent results of this nature.

In this paper we will consider a variant of these problems in which lights are constrained to shine in some specified angles of illumination: Given n points in the plane which are to be the positions of n oodlights, and given n planar angles representing the arcs of illumination of the oodlights, decide how to assign the oodlights to the points and how to fix their rotational angles, in order to light up some target. A harder problem is to minimize the number of oodlights needed. We will consider two types of target: a line segment (or stage"), and the whole plane.

At a recent workshop, Jorge Urrutia posed the version of this problem for lighting up a stage. This Stage Light" problem seems difficult. In section 3 we give a counterexample to an intuitively plausible greedy algorithm.

* Part of this work was carried out when the authors were participants of the 1992 Workshop on Graph Theory and Computational Geometry at the Bellairs Research Institute of McGill University. A preliminary version appeared in the Proceedings of the 5th Canadian Conference on Computational Geometry, 1993.
1 Dept. Computer Science, McGill Univ., Montreal, Canada. jit@muff.cs.mcgill.ca
2 Computer Science Dept., Stanford Univ., Palo Alto, California, USA 94301. guibas@src.dec.com 3 Dept. Computer Science, Univ. of Waterloo, Waterloo, Canada, N2L 3G1. Supported in part by NSERC. alubiw@uwaterloo.ca
4 Dept. Computer Science, Univ. of Utrecht, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands. Supported in part by the Netherlands Organization for Scientific Research (NWO). markov@cs.ruu.nl
5 Dept. Computer Science, Rutgers Univ., New Brunswick, New Jersey, USA 08903. Supported in part by NSF Grant CCR-91-04732. dls@cs.rutgers.edu
6 Dept. of Computer Science, Univ. of Ottawa, Ottawa, Ontario, Canada, K1N 6N5. jorge@csi.uottawa.ca