License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.34
URN: urn:nbn:de:0030-drops-63850
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6385/
Go to the corresponding LIPIcs Volume Portal

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

On Interference Among Moving Sensors and Related Problems

pdf-format:
LIPIcs-ESA-2016-34.pdf (0.5 MB)

Abstract

We show that for any set of n moving points in R^d 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)^0.5). This is optimal up to an O((log n)^0.5) factor.

BibTeX - Entry

@InProceedings{decarufel_et_al:LIPIcs:2016:6385,
  author =	{Jean-Lou De Carufel and Matthew J. Katz and Matias Korman and Andr{\'e} van Renssen and Marcel Roeloffzen and Shakhar Smorodinsky},
  title =	{{On Interference Among Moving Sensors and Related Problems}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{34:1--34:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6385},
  URN =		{urn:nbn:de:0030-drops-63850},
  doi =		{10.4230/LIPIcs.ESA.2016.34},
  annote =	{Keywords: Range spaces, Voronoi diagrams, moving points, facility location, interference minimization}
}

Keywords: Range spaces, Voronoi diagrams, moving points, facility location, interference minimization
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI