Optimization Methods in Discrete Geometry

Dissertation, Freie Universität Berlin
Author: Moritz Firsching
Advisor: G√ľnter M. Ziegler
Full text: journal

In this thesis we study some problems from discrete geometry and develop new methods for solving them. Many such problems can be formulated as optimization problems over spaces defined by systems of polynomial inequalities.

Our method consists of two steps, which can be summarized as follows: Model a problem from discrete geometry as a system of polynomial inequalities and solve it numerically. From the numerical solution, derive an exact solution, which may provide additional structural information.

For any specific problem, each of these two steps needs to be adapted. We illustrate this approach in different applications ranging from the classification of polytopes to packing problems.