Coverage with k-transmitters in the presence of obstacles

Brad Ballinger; Nadia Benbernou; Prosenjit Bose; Mirela Damian; Erik D. Demaine; Vida Dujmović; Robin Flatland; Ferran Hurtado; John Iacono; Anna Lubiw; Pat Morin; Vera Sacristán; Diane Souvaine; Ryuhei Uehara

doi:10.1007/978-3-642-17461-2_1

Coverage with k-transmitters in the presence of obstacles

Brad Ballinger, Nadia Benbernou, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Vida Dujmović, Robin Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristán, Diane Souvaine, Ryuhei Uehara

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

For a fixed integer k ≥ 0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k "walls", represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons.

Original language	English (US)
Title of host publication	Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings
Pages	1-15
Number of pages	15
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-17461-2_1
State	Published - 2010
Event	4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010 - Kailua-Kona, HI, United States Duration: Dec 18 2010 → Dec 20 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	6509 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010
Country/Territory	United States
City	Kailua-Kona, HI
Period	12/18/10 → 12/20/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-17461-2_1

Cite this

Ballinger, B., Benbernou, N., Bose, P., Damian, M., Demaine, E. D., Dujmović, V., Flatland, R., Hurtado, F., Iacono, J., Lubiw, A., Morin, P., Sacristán, V., Souvaine, D., & Uehara, R. (2010). Coverage with k-transmitters in the presence of obstacles. In Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings (PART 2 ed., pp. 1-15). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6509 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-17461-2_1

Coverage with k-transmitters in the presence of obstacles. / Ballinger, Brad; Benbernou, Nadia; Bose, Prosenjit et al.
Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings. PART 2. ed. 2010. p. 1-15 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6509 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ballinger, B, Benbernou, N, Bose, P, Damian, M, Demaine, ED, Dujmović, V, Flatland, R, Hurtado, F, Iacono, J, Lubiw, A, Morin, P, Sacristán, V, Souvaine, D & Uehara, R 2010, Coverage with k-transmitters in the presence of obstacles. in Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6509 LNCS, pp. 1-15, 4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010, Kailua-Kona, HI, United States, 12/18/10. https://doi.org/10.1007/978-3-642-17461-2_1

Ballinger B, Benbernou N, Bose P, Damian M, Demaine ED, Dujmović V et al. Coverage with k-transmitters in the presence of obstacles. In Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings. PART 2 ed. 2010. p. 1-15. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-17461-2_1

Ballinger, Brad ; Benbernou, Nadia ; Bose, Prosenjit et al. / Coverage with k-transmitters in the presence of obstacles. Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings. PART 2. ed. 2010. pp. 1-15 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{d52a9b55281a41d68887f7261f35ed89,

title = "Coverage with k-transmitters in the presence of obstacles",

abstract = "For a fixed integer k ≥ 0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k {"}walls{"}, represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons.",

author = "Brad Ballinger and Nadia Benbernou and Prosenjit Bose and Mirela Damian and Demaine, {Erik D.} and Vida Dujmovi{\'c} and Robin Flatland and Ferran Hurtado and John Iacono and Anna Lubiw and Pat Morin and Vera Sacrist{\'a}n and Diane Souvaine and Ryuhei Uehara",

note = "Funding Information: ★ Supported by NSF grant CCF-0728909. ★★ Partially supported by projects MTM2009-07242 and Gen. Cat. DGR 2009SGR1040.; 4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010 ; Conference date: 18-12-2010 Through 20-12-2010",

year = "2010",

doi = "10.1007/978-3-642-17461-2_1",

language = "English (US)",

isbn = "3642174604",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "1--15",

booktitle = "Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings",

edition = "PART 2",

}

TY - GEN

T1 - Coverage with k-transmitters in the presence of obstacles

AU - Ballinger, Brad

AU - Benbernou, Nadia

AU - Bose, Prosenjit

AU - Damian, Mirela

AU - Demaine, Erik D.

AU - Dujmović, Vida

AU - Flatland, Robin

AU - Hurtado, Ferran

AU - Iacono, John

AU - Lubiw, Anna

AU - Morin, Pat

AU - Sacristán, Vera

AU - Souvaine, Diane

AU - Uehara, Ryuhei

N1 - Funding Information: ★ Supported by NSF grant CCF-0728909. ★★ Partially supported by projects MTM2009-07242 and Gen. Cat. DGR 2009SGR1040.

PY - 2010

Y1 - 2010

N2 - For a fixed integer k ≥ 0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k "walls", represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons.

AB - For a fixed integer k ≥ 0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k "walls", represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons.

UR - http://www.scopus.com/inward/record.url?scp=78650801307&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650801307&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17461-2_1

DO - 10.1007/978-3-642-17461-2_1

M3 - Conference contribution

AN - SCOPUS:78650801307

SN - 3642174604

SN - 9783642174605

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 15

BT - Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings

T2 - 4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010

Y2 - 18 December 2010 through 20 December 2010

ER -

Coverage with k-transmitters in the presence of obstacles

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this