# On interference among moving sensors and related problems Academic Article

•
• Overview
•
• We show that for any set of $n$ moving points 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 isbalanced''at any given time (ie, 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 an application, 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})$. This is optimal up to an $O (\sqrt {\log n})$ factor. In order to obtain these results, we extend well-known results from $\varepsilon$-net theory to kinetic environments.