Weak and strong epsilon-nets for geometric range spaces
Saurabh Ray · Publications of the UdS (Saarland University) · 2009
This thesis deals with strong and weak ǫ-nets in geometry and related problems. In the first half of the thesis we look at strong ǫ-nets and the closely related problem of finding minimum hitting sets. We give a new technique for proving the existence of small ǫ-nets for several geometric range spaces. Our technique also gives efficient algorithms to compute small ǫ-nets. By a well known reduction due to Bronimann and Goodrich [10], our results imply constant factor approximation algorithms for the corresponding minimum hitting set problems. We show how the approximation factor given by this standard technique can be improved by giving the first polynomial time approximation scheme for some of the minimum hitting set problems. The algorithm is a very simple and is based on local search. In the second half of the thesis, we turn to weak ǫ-nets, a very important generalization of the idea of strong ǫ-nets for convex ranges. We first consider the simplest example of a weak ǫ-net, namely the centerpoint. We give a new and arguably simpler proof of the well known centerpoint theorem (and also Helly's theorem) in any dimension and use the same idea to prove an optimal generalization of the centerpoint to two points in the plane. Our technique also gives several improved results for small weak ǫ-nets in the plane. We finally look at the general weak ǫ-net problem is d-dimensions. A long standing conjecture states that weak ǫ-nets of size O(ǫ−1polylogǫ−1) exist for convex sets in any dimension. It turns out that if the conjecture is true then it should be possible to construct a weak ǫ-net from a small number of input points. We show that this is indeed true and it is possible to construct a weak ǫ-net from O(ǫ−1polylogǫ−1) input points. We also show an interesting connection between weak and strong ǫ-nets which shows how random sampling can be used to construct weak ǫ-nets. Diese Arbeit beschaftigt sich mit ǫ-nets in der Geometrie und verwandten Problemen. Im ersten Teil der Arbeit werden starke ǫ-nets und das eng verwandte Minimum Hitting Set Problem betrachtet. Es wird eine neue Technik vorgestellt mit deren Hilfe die Existenz von kleinen ǫ-nets in verschiedenen geometrischen Bereichsraumen nachgewiesen werden kann. Diese Technik liefert auch effiziente Algorithmen um kleine ǫ-nets zu berechnen. Mit der bekannten Reduktion von Bronimann und Goodrich [10], fuhrt dies zu Approximationsalgorithmen mit konstantem Faktor fur die entsprechenden Hitting Set Probleme. Der Approximationsfaktor kann sogar verbessert werden durch einen relative einfachen, auf lokaler Suche basierenden Ansatz, der zu dem ersten polynomiellen Approximationsschema fuhrt. Der zweite Teil der Arbeit ist den schwachen ǫ-nets gewidmet die eine wichtige Verallgemeinerung der starken ǫ-nets in konvexen Bereichen darstellen. Zunachst wird der einfachste Fall der schwachen ǫ-nets betrachtet, der Centerpoint. Es wird ein neuer, einfacherer Beweis fur das bekannte Centerpoint Theorem (und ebenso Helly's Theorem) in beliebiger Dimension gezeigt. Die gleiche Idee lasst sich auch benutzen um eine optimale Verallgemeinerung der Centerpoints zu zwei Punkten in der Ebene zu zeigen. Mit dieser Technik konnen verschiedene Resultate fur schwache ǫ-nets in der Ebene verbessert werden. Abschliesend wird das allgemeine schwache ǫ-net Problem in d Dimensionen betrachtet. Eine langjahrige Vermutung besagt, dass schwache ǫ-nets der Grosse O(ǫ−1polylogǫ−1) fur konvexe Mengen in jeder Dimension existieren. Es stellt sich heraus, dass wenn sich die Vermutung als wahr erweist, dann ist es moglich ein schwaches ǫ-net aus einer kleinen Menge von Inputpunkten zu erzeugen. In dieser Arbeit wird gezeigt, dass dies tatsachlich moglich ist und ein schwaches ǫ-net aus O(ǫ−1polylogǫ−1) Inputpunkten erzeugt werden kann. Letztendlich lasst sich ein interessanter Zusammenhang zwischen schwachen und starken ǫ-nets zeigen durch den schwache ǫ-nets durch eine Zufallsauswahl konstruiert werden konnen.