On Interference Among Moving Sensors and Related Problems

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

doi:10.4230/LIPIcs.ESA.2016.34

File

LIPIcs.ESA.2016.34.pdf

Filesize: 495 kB
11 pages

Document Identifiers

DOI: 10.4230/LIPIcs.ESA.2016.34
URN: urn:nbn:de:0030-drops-63850

Author Details

Jean-Lou De Carufel

Matthew J. Katz

Matias Korman

André van Renssen

Marcel Roeloffzen

Shakhar Smorodinsky

Cite AsGet BibTex

Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, and Shakhar Smorodinsky. On Interference Among Moving Sensors and Related Problems. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.34

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.

Keywords

Range spaces
Voronoi diagrams
moving points
facility location
interference minimization

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

N. Alon. A non-linear lower bound for planar epsilon-nets. Discrete & Computational Geometry, 47(2):235-244, 2012. URL: http://dx.doi.org/10.1007/s00454-010-9323-7.
B. Aronov, E. Ezra, and M. Sharir. Small-size epsilon-nets for axis-parallel rectangles and boxes. SIAM Journal on Computing, 39(7):3248-3282, 2010.
K. Böröczky. Packing of spheres in spaces of constant curvature. Acta Mathematica Academiae Scientiarum Hungarica, 32(3-4):243-261, 1978. URL: http://dx.doi.org/10.1007/BF01902361.
Y. Brise, K. Buchin, D. Eversmann, M. Hoffmann, and W. Mulzer. Interference minimization in asymmetric sensor networks. In ALGOSENSORS 2014, pages 136-151, 2014. URL: http://dx.doi.org/10.1007/978-3-662-46018-4_9.
J.-L. De Carufel, M. Katz, M. Korman, A. van Renssen, M. Roeloffzen, and S. Smorodinsky. On kinetic range spaces and their applications. CoRR, abs/1507.02130, 2015. URL: http://arxiv.org/abs/1507.02130.
M.M. Halldórsson and T. Tokuyama. Minimizing interference of a wireless ad-hoc network in a plane. Theoretical Computer Science, 402(1):29-42, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.03.003.
D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987.
J. Komlós, J. Pach, and G.J. Woeginger. Almost tight bounds for epsilon-nets. Discrete & Computational Geometry, 7:163-173, 1992.
M. Korman. Minimizing interference in ad-hoc networks with bounded communication radius. Information Processing Letters, 112(19):748-752, 2012. URL: http://dx.doi.org/10.1016/j.ipl.2012.06.021.
J. Matoušek. Approximations and optimal geometric divide-and-conquer. In Symposium on the Theory of Computing, pages 505-511, 1991.
J. Matoušek. Lectures on Discrete Geometry. Springer-Verlag New York, Inc., 2002.
G. Nivasch. Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations. Journal of the ACM, 57(3), 2010.
J. Pach and P. K. Agarwal. Combinatorial Geometry. Wiley Interscience, 1995.
J. Pach and G. Tardos. Tight lower bounds for the size of epsilon-nets. In Symposium on Computational Geometry, pages 458-463, 2011.
M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971.
P. von Rickenbach, R. Wattenhofer, and A. Zollinger. Algorithmic models of interference in wireless ad hoc and sensor networks. IEEE/ACM transactions on sensor networks, 17(1):172-185, 2009. URL: http://dx.doi.org/10.1109/TNET.2008.926506.