Back to Search Start Over

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

Authors :
Rok, Alexandre
Smorodinsky, Shakhar
Publication Year :
2015

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.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1512.07505
Document Type :
Working Paper