# Item

ITEM ACTIONSEXPORT

Released

Thesis

#### Weak and Strong ε-Nets for Geometric Range Spaces

##### External Resource

http://scidok.sulb.uni-saarland.de/volltexte/2009/2567/

(Any fulltext)

http://scidok.sulb.uni-saarland.de/doku/lic_ohne_pod.php?la=de

(Copyright transfer agreement)

##### 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

##### Citation

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

##### 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(

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.

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.