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

•
• Overview
•

### abstract

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