engleski

Geometric Optimization and Querying -- Exact and Approximate

This thesis has two main parts. The first part deals with the stage illumination problem. Given a stage represented by a line segment L and a set of lightsources represented by a set of points S 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. We present different solutions, based on convex optimization, discretization and linear programming, as well as a purely combinatorial approximation algorithm. Some experimental results are also provided. 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 efcient queries. The central idea of our data structures is the well-separated pair decomposition. The first problem we address is the k-hop restricted shortest path under the power-euclidean distance function. The second problem in this part is so-called cone-restricted nearest neighbor. For a given point set in Euclidean space we consider the problem of nding (approximate) nearest neighbors of a query point but restricting only to points that lie within a fixed cone with apex at the query point. We investigate the structure of the Voronoi diagram induced by this notion of proximity and present approximate and exact data structures for answering cone-restricted nearest neighbor queries.

Compinatorial optimization; Computational Geometry; Approximation Algorithms

nije evidentirano