Illuminating a Convex Polygon Optimally with Three Floodlights

by    A. Spillner

Preprint series: 03-18, Reports on Computer Science

Preprint series: , 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 convex polygon \(P\) and want to illuminate \(P\) with
three floodlights (whose apices are located in \(P\)) such
that the sum of their sizes is minimized.
We present an \(O(n^2)\) time algorithm that solves this
problem using \(O(n)\) space where \(n\) is the number of
vertices of \(P\). Our model of computation is the real RAM.

Keywords: illumination, floodlight

Upload: 2004-01-07

Update: 2004-01-07


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