Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25956
Titel: Weak and strong epsilon-nets for geometric range spaces
VerfasserIn: Ray, Saurabh
Sprache: Englisch
Erscheinungsjahr: 2009
Kontrollierte Schlagwörter: Geometrie
Algorithmus
Approximationsalgorithmus
Freie Schlagwörter: 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-Sachgruppe: 004 Informatik
Dokumenttyp: Dissertation
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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-25676
hdl:20.500.11880/26012
http://dx.doi.org/10.22028/D291-25956
Erstgutachter: Seidel, Raimund
Tag der mündlichen Prüfung: 25-Mai-2009
Datum des Eintrags: 18-Nov-2009
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
Dissertation_1536_Ray_Saur_2009.pdf530,67 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.