Geometrical and combinatorial optimization problems

In this habilitation thesis several geometrical and combinatorial optimization problems are considered. First we introduce the facility location ratio which is the supremum of the quotient of the cost of an optimal solution and the minimum cost of a solution where all facilities are lying on client positions over all facility location instances. We derive upper and lower bounds for the facility location ratio for several metrics. In the rectilinear Steiner arborescence problem the task is to build a shortest rectilinear Steiner tree connecting a given root and a set of terminals which are placed in the plane such that all root-terminal-paths are shortest paths. We prove that a more restricted version of this problem where the number of vertices on each of these paths is given is NP-hard. Moreover, we consider the problem of embedding the Steiner points of a Steiner tree with a given topology into the rectilinear plane. Thereby, the length of the path between a distinguished terminal and each other terminal must not exceed given length restrictions. We show that the problem can be formulated as a linear program and present the first combinatorial polynomial time algorithm for the problem. Then we present the first polynomial time algorithm for building binary trees with choosable edge lengths. Here the task is to build a binary tree with leaves at given depths and assign integral length to the edges of the tree such that the length of the two edges leaving a vertex always sum up to a given constant. Finally, we establish a new framework to obtain upper bounds for the number of guards necessary to guards rectilinear art galleries