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.

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)