Geometric Set Systems
Jiřı́ Matoušek · Progress in mathematics · 1998
Let X be a finite point set in the plane. We consider the set system on X whose sets are all intersections of X with a halfplane. Similarly one can investigate set systems defined on point sets in higher-dimensional spaces by other classes of simple geometric figures (simplices, balls, ellipsoids, etc.). It turns out that simple combinatorial properties of such set systems (most notably the Vapnik-Chervonenkis dimension and related concepts of shatter functions ) play an important role in several areas of mathematics and theoretical computer science. Here we concentrate on applications in discrepancy theory, in combinatorial geometry, in derandomization of geometric algorithms, and in geometric range searching. We believe that the tools described might be useful in other areas of mathematics too. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.