On interference among moving sensors and related problems

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

doi:10.4230/LIPIcs.ESA.2016.34

On interference among moving sensors and related problems

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

137 Downloads (Pure)

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). This is optimal up to an O(√log n) factor.

Original language	English
Title of host publication	24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark
Editors	P. Sankowski, C. Zaroliagis
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	11
ISBN (Electronic)	9783959770156
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2016.34
Publication status	Published - 1 Aug 2016
Externally published	Yes
Event	24th Annual European Symposium on Algorithms (ESA 2016) - Aarhus, Denmark Duration: 22 Aug 2016 → 24 Aug 2016 Conference number: 24 http://conferences.au.dk/algo16/esa/

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	57
ISSN (Print)	1868-8969

Conference

Conference	24th Annual European Symposium on Algorithms (ESA 2016)
Abbreviated title	ESA 2016
Country/Territory	Denmark
City	Aarhus
Period	22/08/16 → 24/08/16
Internet address	http://conferences.au.dk/algo16/esa/

Funding

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.

Keywords

Facility location
Interference minimization
Moving points
Range spaces
Voronoi diagrams

Access to Document

10.4230/LIPIcs.ESA.2016.34

publishers versionFinal published version, 498 KBLicence: CC BY

Cite this

De Carufel, J. L., Katz, M. J., Korman, M., van Renssen, A., Roeloffzen, M., & Smorodinsky, S. (2016). On interference among moving sensors and related problems. In P. Sankowski, & C. Zaroliagis (Eds.), 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark Article 34 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 57). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2016.34

De Carufel, Jean Lou ; Katz, Matthew J. ; Korman, Matias et al. / On interference among moving sensors and related problems. 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark. editor / P. Sankowski ; C. Zaroliagis. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{4364a76908fa4b1c82b0828c758a51e2,

title = "On interference among moving sensors and related problems",

abstract = "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.",

keywords = "Facility location, Interference minimization, Moving points, Range spaces, Voronoi diagrams",

author = "\{De Carufel\}, \{Jean Lou\} and Katz, \{Matthew J.\} and Matias Korman and \{van Renssen\}, Andr{\'e} and Marcel Roeloffzen and Shakhar Smorodinsky",

year = "2016",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.ESA.2016.34",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "P. Sankowski and C. Zaroliagis",

booktitle = "24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark",

note = "24th Annual European Symposium on Algorithms (ESA 2016), ESA 2016 ; Conference date: 22-08-2016 Through 24-08-2016",

url = "http://conferences.au.dk/algo16/esa/",

}

De Carufel, JL, Katz, MJ, Korman, M, van Renssen, A, Roeloffzen, M & Smorodinsky, S 2016, On interference among moving sensors and related problems. in P Sankowski & C Zaroliagis (eds), 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark., 34, Leibniz International Proceedings in Informatics (LIPIcs), vol. 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 22/08/16. https://doi.org/10.4230/LIPIcs.ESA.2016.34

On interference among moving sensors and related problems. / De Carufel, Jean Lou; Katz, Matthew J.; Korman, Matias et al.
24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark. ed. / P. Sankowski; C. Zaroliagis. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. 34 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 57).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 - Conference code: 24

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 - https://www.scopus.com/pages/publications/85012965402

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, August 22-24, 2016, Aarhus, Denmark

A2 - Sankowski, P.

A2 - Zaroliagis, C.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

T2 - 24th Annual European Symposium on Algorithms (ESA 2016)

Y2 - 22 August 2016 through 24 August 2016

ER -

De Carufel JL, Katz MJ, Korman M, van Renssen A, Roeloffzen M, Smorodinsky S. On interference among moving sensors and related problems. In Sankowski P, Zaroliagis C, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2016. 34. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.ESA.2016.34

On interference among moving sensors and related problems

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this