Please use this identifier to cite or link to this item: doi:10.22028/D291-25956
Title: Weak and strong epsilon-nets for geometric range spaces
Author(s): Ray, Saurabh
Language: English
Year of Publication: 2009
SWD key words: Geometrie
Algorithmus
Approximationsalgorithmus
Free key words: Epsilon-Net
Centerpoint-Theorem
Helly's Theorem
Minimum Hitting Set Problem
geometry
geometric range space
epsilon-net
minimum hitting set
centerpoint theorem
Helly's theorem
algorithm
approximation algorithm
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: 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 beschäftigt 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 Bereichsräumen nachgewiesen werden kann. Diese Technik liefert auch effiziente Algorithmen um kleine ǫ-nets zu berechnen. Mit der bekannten Reduktion von Bronimann und Goodrich [10], führt dies zu Approximationsalgorithmen mit konstantem Faktor für 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 führt. Der zweite Teil der Arbeit ist den schwachen ǫ-nets gewidmet die eine wichtige Verallgemeinerung der starken ǫ-nets in konvexen Bereichen darstellen. Zunächst wird der einfachste Fall der schwachen ǫ-nets betrachtet, der Centerpoint. Es wird ein neuer, einfacherer Beweis für das bekannte Centerpoint Theorem (und ebenso Helly's Theorem) in beliebiger Dimension gezeigt. Die gleiche Idee lässt sich auch benutzen um eine optimale Verallgemeinerung der Centerpoints zu zwei Punkten in der Ebene zu zeigen. Mit dieser Technik können verschiedene Resultate für schwache ǫ-nets in der Ebene verbessert werden. Abschließend wird das allgemeine schwache ǫ-net Problem in d Dimensionen betrachtet. Eine langjährige Vermutung besagt, dass schwache ǫ-nets der Grösse O(ǫ−1polylogǫ−1) für konvexe Mengen in jeder Dimension existieren. Es stellt sich heraus, dass wenn sich die Vermutung als wahr erweist, dann ist es möglich ein schwaches ǫ-net aus einer kleinen Menge von Inputpunkten zu erzeugen. In dieser Arbeit wird gezeigt, dass dies tatsächlich möglich ist und ein schwaches ǫ-net aus O(ǫ−1polylogǫ−1) Inputpunkten erzeugt werden kann. Letztendlich lässt sich ein interessanter Zusammenhang zwischen schwachen und starken ǫ-nets zeigen durch den schwache ǫ-nets durch eine Zufallsauswahl konstruiert werden können.
Link to this record: urn:nbn:de:bsz:291-scidok-25676
hdl:20.500.11880/26012
http://dx.doi.org/10.22028/D291-25956
Advisor: Seidel, Raimund
Date of oral examination: 25-May-2009
Date of registration: 18-Nov-2009
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Dissertation_1536_Ray_Saur_2009.pdf530,67 kBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.