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


  • Abstract: We study geometric hypergrahs in a kinetic setting. That is, the set of vertices of the hypergraph is a set of moving points in $\Re^ d $ with coordinates that are polynomials in time. The hyperedges are all subsets that can be realized by intersecting the set of points at some fixed time with some" simple" geometric shape, such as, say, a halfspace. We show that for many of the static cases where the\VC-dimension of the hypergraph is bounded, the kinetic counterpart also has bounded\VC-dimension. This allows us to prove our main result: for any set of $ n $ moving points in $\Re^ d $ and any parameter $1< k< n $, one can select a 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. By that, we mean that at any time, each Voronoi cell contains at most $ O (n/k) $ of the points. We also show that the bound $ O (k\log k) $ is …

publication date

  • January 1, 2015

published in