Back to Search
Start Over
A short proof of the first selection lemma and weak $\frac{1}{r}$-nets for moving points
- 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.
- Subjects :
- Computer Science - Discrete Mathematics
F.2.2
G.2.1
G.2.2
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1512.07505
- Document Type :
- Working Paper