AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS   Info

AG Audience

English

60 Minutes

Saarbrücken

This thesis has two main parts. The first part deals with "the stage illumination problem". Given a stage represented by a line segment and a set of lightsources represented by a set of points in the plane, assign powers to the lightsources such that every point on the stage receives a sufficient amount, e.g. one unit, of light while minimizing the overall power consumption. By assuming that the amount of light arriving from a fixed lightsource decreases rapidly with the distance from the lightsource, this becomes an interesting geometric optimization problem.

In the second part of this thesis, we are concerned with two different geometric problems whose solutions are based on the construction of a data structure that would allow for efficient queries. The central idea of our data structures is the "well-separated pair decomposition".

Domagoj Matijevic

114

--email hidden

passcode not visible

logged in users only

Computational Geometry, Approximation Algorithms