On interference among moving sensors and related problems Academic Article uri icon


  • 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 is``balanced''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.

publication date

  • April 25, 2017