A short proof of the first selection lemma and weak $\frac {1}{r} $-nets for moving points Academic Article uri icon


  • (i) We provide a short and simple proof of the first selection lemma.(ii) We also prove a selection lemma of a new type in $\Re^ d $. For example, when $ d= 2$ assuming $ n $ is large enough we prove that for any set $ P $ of $ n $ points in general position there are $\Omega (n^ 4) $ pairs of segments spanned by $ P $ all of which intersect in some fixed triangle spanned by $ P $.(iii) Finally, we extend the weak $\frac {1}{r} $-net theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog $ N $ of a weak $\frac {1}{r} $-net of cardinality $ O (r^{\frac {d (d+ 1)}{2}}\log^{d} r) $ whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of $ N $ has one polynomial coordinate. Subjects: Discrete Mathematics (cs. DM) …

publication date

  • December 23, 2015