  We show that for any set of $n$ points moving along "simple" trajectories
(i.e., each coordinate is described with a polynomial of bounded degree) in
$\Re^d$ and any parameter $2 \le k \le n$, one can select a fixed non-empty
subset of the points of size $O(k \log k)$, such that the Voronoi diagram of
this subset is "balanced" at any given time (i.e., it contains $O(n/k)$ points
per cell). We also show that the bound $O(k \log k)$ is near optimal even for
the one dimensional case in which points move linearly in time. As
applications, we show that one can assign communication radii to the sensors of
a network of $n$ moving sensors so that at any given time their interference is
$O(\sqrt{n\log n})$. We also show some results in kinetic approximate range
counting and kinetic discrepancy. In order to obtain these results, we extend
well-known results from $\varepsilon$-net theory to kinetic environments.

Computational Geometry;Discrete Mathematics;Combinatorics