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/s10878-012-9475-x

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: Contribution to journal › Article › peer-review

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)
Pages (from-to)	208-233
Number of pages	26
Journal	Journal of Combinatorial Optimization
Volume	25
Issue number	2
DOIs	https://doi.org/10.1007/s10878-012-9475-x
State	Published - Feb 2013

Keywords

Art gallery
Coverage
Guarding
Transmitters
Visibility

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-012-9475-x

Cite this

@article{88aada3372f84a50b49bb727d23525f7,

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

keywords = "Art gallery, Coverage, Guarding, Transmitters, Visibility",

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: F. Hurtado and V. Sacrist{\'a}n were partly supported by the ESF EUROCORES programme EUROGIGA-ComPoSe IP04-MICINN Project EUI-EURC-2011-4306, and projects MTM2009-07242 and Gen. Cat. DGR 2009SGR1040. M. Damian was partly supported by NSF grant CCF-0728909.",

year = "2013",

month = feb,

doi = "10.1007/s10878-012-9475-x",

language = "English (US)",

volume = "25",

pages = "208--233",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

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: F. Hurtado and V. Sacristán were partly supported by the ESF EUROCORES programme EUROGIGA-ComPoSe IP04-MICINN Project EUI-EURC-2011-4306, and projects MTM2009-07242 and Gen. Cat. DGR 2009SGR1040. M. Damian was partly supported by NSF grant CCF-0728909.

PY - 2013/2

Y1 - 2013/2

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.

KW - Art gallery

KW - Coverage

KW - Guarding

KW - Transmitters

KW - Visibility

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

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

U2 - 10.1007/s10878-012-9475-x

DO - 10.1007/s10878-012-9475-x

M3 - Article

AN - SCOPUS:84879552767

SN - 1382-6905

VL - 25

SP - 208

EP - 233

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

ER -

Coverage with k-transmitters in the presence of obstacles

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this