On interference among moving sensors and related problems

DOI10.4230/LIPICS.ESA.2016.34zbMATH Open1397.68200arXiv1507.02130MaRDI QIDQ4606303FDOQ4606303

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

Publication date: 2 March 2018

Abstract: We show that for any set of $n$ points moving along "simple" trajectories (i.e., each coordinate is described with a polynomial of bounded degree) in $R{e}^d$ and any parameter $2leklen$, one can select a fixed non-empty subset of the points of size $O(klogk)$, 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(klogk)$ is near optimal even for the one dimensional case in which points move linearly in time. As applications, 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(sqrtnlogn)$. We also show some results in kinetic approximate range counting and kinetic discrepancy. In order to obtain these results, we extend well-known results from $varepsilon$-net theory to kinetic environments.

Full work available at URL: https://arxiv.org/abs/1507.02130

Recommendations

• On interference among moving sensors and related problems
• Displacing random sensors to avoid interference
• Maximum interference of random sensors on a line
• Minimizing interference in ad-hoc networks with bounded communication radius
• Minimizing Interference Potential Among Moving Entities

zbMATH Keywords

facility locationVoronoi diagramsmoving pointsrange spacesinterference minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Cited In (2)

• Minimizing Interference Potential Among Moving Entities
• Maximum interference of random sensors on a line

This page was built for publication: On interference among moving sensors and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606303)