2026-07-22T01:29:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6385 2024-03-06T10:38:07Z ddc:004 open_access

On Interference Among Moving Sensors and Related Problems De Carufel, Jean-Lou Katz, Matthew J. Korman, Matias van Renssen, André Roeloffzen, Marcel Smorodinsky, Shakhar Range spaces Voronoi diagrams moving points facility location interference minimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jean-Lou De Carufel and Matthew J. Katz and Matias Korman and André van Renssen and Marcel Roeloffzen and Shakhar Smorodinsky 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.34 urn:nbn:de:0030-drops-63850 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.34 eng https://creativecommons.org/licenses/by/3.0/legalcode