Paper by Erik D. Demaine

Reference:

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, and Ryuhei Uehara, “Coverage with k-Transmitters in the Presence of Obstacles”, in Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010), Lecture Notes in Computer Science, volume 6509, The Big Island, Hawaii, USA, December 18–20, 2010, pages 627–652.

BibTeX

@InProceedings{Transmitters_COCOA2010,
  AUTHOR        = {Brad Ballinger and Nadia Benbernou and Prosenjit Bose and
                   Mirela Damian and Erik D. Demaine 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},
  TITLE         = {Coverage with $k$-Transmitters in the Presence of Obstacles},
  BOOKTITLE     = {Proceedings of the 4th Annual International Conference on
                   Combinatorial Optimization and Applications (COCOA 2010)},
  bookurl       = {http://theory.utdallas.edu/COCOA2010/},
  ADDRESS       = {The Big Island, Hawaii, USA},
  MONTH         = {December 18--20},
  YEAR          = 2010,
  PAGES         = {627--652},
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 6509,

  papers        = {Transmitters_JOCO},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-642-17461-2_1},
  dblp          = {https://dblp.org/rec/conf/cocoa/BallingerBBDDDFHILa10},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-17461-2_1">SpringerLink</A>.},
}

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.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (484k).

See information on file formats.

[Google Scholar search]

Related papers:

Transmitters_JOCO (Coverage with k-Transmitters in the Presence of Obstacles)