hide
Free keywords:

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
ddimensions. 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.