On interference among moving sensors and related problems

Jean Lou De Carufel, Matthew J. Katz, Matias Korman, André Van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


We show that for any set of n moving points in Rd and any parameter 2 ≤ k ≤ 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 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(√n log n). This is optimal up to an O(√log n) factor.

Original languageEnglish
Title of host publication24th Annual European Symposium on Algorithms, ESA 2016
EditorsChristos Zaroliagis, Piotr Sankowski
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770156
Publication statusPublished - 2016 Aug 1
Event24th Annual European Symposium on Algorithms, ESA 2016 - Aarhus, Denmark
Duration: 2016 Aug 222016 Aug 24

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other24th Annual European Symposium on Algorithms, ESA 2016


  • Facility location
  • Interference minimization
  • Moving points
  • Range spaces
  • Voronoi diagrams

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'On interference among moving sensors and related problems'. Together they form a unique fingerprint.

Cite this