by A. Spillner
Preprint series: 03-18, Reports on Computer Science
Preprint series: , Reports on Computer Science
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