TY - GEN
T1 - On interference among moving sensors and related problems
AU - De Carufel, Jean Lou
AU - Katz, Matthew J.
AU - Korman, Matias
AU - Van Renssen, André
AU - Roeloffzen, Marcel
AU - Smorodinsky, Shakhar
N1 - Funding Information:
M. K. was supported in part by the ELC project (MEXT KAKENHI Nos. 12H00855 and 15H02665). S. S. was partially supported by Grant 1136/12 from the Israel Science Foundation and by the Swiss National Science Foundation Grants 200020144531 and 200021137574.
Publisher Copyright:
© Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - 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.
AB - 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.
KW - Facility location
KW - Interference minimization
KW - Moving points
KW - Range spaces
KW - Voronoi diagrams
UR - http://www.scopus.com/inward/record.url?scp=85012965402&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85012965402&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2016.34
DO - 10.4230/LIPIcs.ESA.2016.34
M3 - Conference contribution
AN - SCOPUS:85012965402
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 24th Annual European Symposium on Algorithms, ESA 2016
A2 - Zaroliagis, Christos
A2 - Sankowski, Piotr
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 24th Annual European Symposium on Algorithms, ESA 2016
Y2 - 22 August 2016 through 24 August 2016
ER -