Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Weak and Strong ε-Nets for Geometric Range Spaces


Ray,  Saurabh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Ray, S. (2009). Weak and Strong ε-Nets for Geometric Range Spaces. PhD Thesis, Universität des Saarlandes, Saarbrücken. doi:10.22028/D291-25956.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0027-B4CA-E
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(
1polylog1) 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(1polylog1) 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.