**Preprint series:** 03-12, Reports on Computer Science

**MSC:**- 68U05 Computer graphics; computational geometry [See also 65D18]
- 65D18 Computer graphics and computational geometry [See also 51N05, 68U05]

**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*

**Upload:** 2003-10-14

The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.