Computational aspects of some problems from discrete geometry in higher dimensions

Abstract

We 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.

In dieser Arbeit betrachten wir algorithmische Aspekte verschiedener Probleme der diskreten Geometrie in höheren Dimensionen. Während viele von ihnen in der Ebene intensiv untersucht und effizient lösbar sind, werden sie deutlich schwieriger, wenn sich die Dimension erhöht. In dieser Arbeit machen wir einen Versuch, dieses Phänomen zu erklären, indem wir zeigen, dass sie im komplexitätstheoretischen Sinne schwer sind. Dazu benutzen wir unter anderem parametrisierte Komplexitätstheorie, die es uns erlaubt, schärfere relative untere Schranken zu zeigen, als sie alleine mit klassischer Komplexitätstheorie möglich sind. Für eines solcher Probleme entwerfen wir außerdem verschiedene Approximationsalgorithmen. Besonderes Augenmerk liegt dabei auf der Untersuchung der exakten Abhängigkeit der Laufzeit von der Dimension. Wir entwerfen und benutzen verschiedene Techniken, um die Schwerheit der Probleme in unbeschränkter Dimension zu zeigen. Ein Beispiel dafür ist die Zerlegung des d-dimensionalen Raumes in orthogonale Ebenen, in die wir bestimmte Teile einer Konstruktion platzieren können. Damit ist es uns möglich, relative untere Schranken von n^\Omega(d) für die Laufzeit von Algorithmen für verschiedene Probleme zu zeigen. Diese beinhalten das Berechnen der Diskrepanz von Punktmengen oder die Verifikation von epsilon- Netzen. Wir stellen anschließend eine etwas natürlichere Reduktionstechnik vor, die vom d-Sum Problem reduziert. Damit zeigen wir relative untere Schranken für einige Entscheidungsprobleme, die zu Sätzen der Diskreten Geometrie gehören. Dieses sind zum Beispiel das Bestimmen einer minimalen Hellymenge, bestimmte Entscheidungsvarianten des Ham-Sandwich Problems, und das Berechnen der Tverbergtiefe eines Punktes. Anschließend wenden wir uns dem Problem zu, eine maximal große Untermenge in konvexer Lage zu finden. Während die bisherigen Probleme durch einfache Algorithmen in n^O(\poly(d)) Zeit lösbar sind, tritt hier das Phänomen auf, dass das Problem schon in 3 Dimensionen NP-schwer ist. Das zeigt einen starken Unterschied zwischen einem niedrig- und einem höherdimensionalen Problem, da es in der Ebene in polynomieller Zeit gelöst werden kann. Für ein positives Ergebnis wenden wir uns dann dem Problem zu, einen Punkt mit hoher Tverbergtiefe in d Dimensionen zu berechnen. Wir entwerfen einen neuen Ansatz, der höherdimensionale aus niedrigdimensionalen Tverbergpunkten berechnet. Unser Algorithmus ist sehr generisch und lässt sich einfach mit bisherigen Algorithmen kombinieren, um noch bessere Resultate zu erhalten. Am Ende geben wir noch einen Ausblick auf mögliche weitere Forschungsvorhaben.