A Note on Optimal Floodlight Illumination of Stages

Preprint series: 03-12, Reports on Computer Science

MSC:

Abstract: In this paper we study the following problem: We are given
a segment $$S$$ of a straight line $$L$$ in the plane and
a finite set $$P$$ of points. $$P$$ is contained in one of
the open halfplanes bounded by $$L$$. We want to illuminate
$$S$$ with floodlights whose apices are located at points
in $$P$$, such that the sum of their sizes is minimized.
We require that no two floodlights share a common
apex. We present an $$O(n\text{log}n)$$ time algorithm that solves
this problem using $$O(n)$$ space where $$n = |P|$$.
Our model of computation is the real RAM.

Keywords: illumination, floodlights