Computational aspects of some problems from discrete geometry in higher dimensions
Werner, Daniel

HaupttitelComputational aspects of some problems from discrete geometry in higher dimensions
TitelvarianteAlgorithmische Aspekte einiger Probleme der diskreten Geometrie in höheren Dimensionen
AutorWerner, Daniel
Geburtsort: Berlin, Deutschland
GutachterProf. Dr. Günter Rote
weitere GutachterProf. Dr. Emo Welzl
Freie Schlagwörtercomputational geometry; discrete geometry; Tverberg-points; centerpoints; ham-sandwich cut; Erdös-Szekeres theorem; epsilon-nets
DDC510 Mathematik
ZusammenfassungWe will investigate computational aspects of several problems from discrete geometry in higher dimensions. In the plane, many of them are well understood and can be solved efficiently, but as the dimension increases, most of them seem to be considerably harder to solve. In this thesis, we make progress towards explaining this phenomenon by showing computational hardness for some of these problems. To this end, we also make use of parameterized complexity theory in order to show stronger relative lower bounds than those possible with classical complexity theory only. For one of the problems, we moreover develop several approximation algorithms. In the process, we pay particular attention to the exact dependence of the running time on the dimension.

We will use and develop different techniques for showing hardness of the problems in unbounded dimension. These include the technique of deconstructing the space into orthogonal planes, into which gadgets are placed. Using this technique, we are able to show a relative lower bound of n^Omega(d) for several problems related to testing the discrepancy of a point set and verifying epsilon-nets.

We then present a more natural reduction technique that reduces from the d-Sum problem to show relative lower bounds for many problems arising from theorems in combinatorial geometry. These include computing minimal Helly sets, certain decision versions of the ham-sandwich problem, and computing the Tverberg depth of a point set.

We then turn to computing a maximum size subset of points in convex position. While all the previous problems admit straightforward n^O(\poly(d)) algorithms in d dimensions, here we are able to show that the problem already becomes hard in 3 dimensions. This shows a strong dichotomy between a low and a higher dimensional case, because in the plane the problem was known to be solvable in polynomial time.

As a positive result, we then consider the problem of computing a point of high Tverberg depth in d dimensions. We present a novel lifting approach that allows us to compute deep points for a point set in high dimension from deep points of its projection to some lower dimensional space. The approach is very generic, and we show how to combine it with other known methods in order to get even better algorithms.

Finally, we give a short outlook and suggest further open problems on the subject.
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
SeitenzahlXIV, 109 S.
Fachbereich/EinrichtungFB Mathematik und Informatik
Rechte Nutzungsbedingungen
Tag der Disputation18.01.2013
Erstellt am22.01.2013 - 08:59:35
Letzte Änderung22.01.2013 - 14:55:04
Statische URLhttp://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000045207