A Note on Optimal Floodlight Illumination of Stages

by    A. Spillner, J. Dietel, H.-D. Hecker

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.