On interference among moving sensors and related problems

DOI10.4230/LIPICS.ESA.2016.34MaRDI QIDQ4606303zbMATH OpenFDO

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

Publication date 2 March 2018

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

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)

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.

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 Potential Among Moving Entities

Cited in

(4)

• On interference among moving sensors and related problems
• Minimizing Interference Potential Among Moving Entities
• Displacing random sensors to avoid interference
• 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)