Coverage with k-Transmitters in the Presence of Obstacles
For a fixed integer k [greater than or equal to] 0, a k-transmitter is an omnidirectional wireless transmitter with an in nite 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-tran...
| Main Authors: | , , , , , , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62801 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826204205329678336 |
|---|---|
| author | Ballinger, Brad Benbernou, Nadia M. Bose, Prosenjit Damian, Mirela Demaine, Erik D. Dujmovic, Vida Flatland, Robin Hurtado, Ferran Iacono, John Lubiw, Anna Morin, Pat Sacristan, Vera Souvaine, Diane Uehara, Ryuhei |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ballinger, Brad Benbernou, Nadia M. Bose, Prosenjit Damian, Mirela Demaine, Erik D. Dujmovic, Vida Flatland, Robin Hurtado, Ferran Iacono, John Lubiw, Anna Morin, Pat Sacristan, Vera Souvaine, Diane Uehara, Ryuhei |
| author_sort | Ballinger, Brad |
| collection | MIT |
| description | For a fixed integer k [greater than or equal to] 0, a k-transmitter is an omnidirectional wireless transmitter with an in nite 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. |
| first_indexed | 2024-09-23T12:50:33Z |
| format | Article |
| id | mit-1721.1/62801 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:50:33Z |
| publishDate | 2011 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/628012022-10-01T11:26:06Z Coverage with k-Transmitters in the Presence of Obstacles Ballinger, Brad Benbernou, Nadia M. Bose, Prosenjit Damian, Mirela Demaine, Erik D. Dujmovic, Vida Flatland, Robin Hurtado, Ferran Iacono, John Lubiw, Anna Morin, Pat Sacristan, Vera Souvaine, Diane Uehara, Ryuhei Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Demaine, Erik D. Demaine, Erik D. Benbernou, Nadia M. For a fixed integer k [greater than or equal to] 0, a k-transmitter is an omnidirectional wireless transmitter with an in nite 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. National Science Foundation (U.S.) (NSF grant CCF-0728909) 2011-05-10T17:39:35Z 2011-05-10T17:39:35Z 2010-12 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-17460-5 3-642-17460-4 http://hdl.handle.net/1721.1/62801 Ballinger, Brad, et al. "Coverage with k-Transmitters in the Presence of Obstacles." COCOA'10, in Proceedings of the 4th International Conference on Combinatorial Optimization and Applications - Volume Part II, Kailua-Kona, Hawaii, USA, Dec. 18-20, 2010. https://orcid.org/0000-0003-3803-5703 en_US http://portal.acm.org/citation.cfm?id=1940425 Proceedings of the 4th International Conference on Combinatorial optimization and applications - Volume Part II, COCOA'10 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Ballinger, Brad Benbernou, Nadia M. Bose, Prosenjit Damian, Mirela Demaine, Erik D. Dujmovic, Vida Flatland, Robin Hurtado, Ferran Iacono, John Lubiw, Anna Morin, Pat Sacristan, Vera Souvaine, Diane Uehara, Ryuhei Coverage with k-Transmitters in the Presence of Obstacles |
| title | Coverage with k-Transmitters in the Presence of Obstacles |
| title_full | Coverage with k-Transmitters in the Presence of Obstacles |
| title_fullStr | Coverage with k-Transmitters in the Presence of Obstacles |
| title_full_unstemmed | Coverage with k-Transmitters in the Presence of Obstacles |
| title_short | Coverage with k-Transmitters in the Presence of Obstacles |
| title_sort | coverage with k transmitters in the presence of obstacles |
| url | http://hdl.handle.net/1721.1/62801 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT ballingerbrad coveragewithktransmittersinthepresenceofobstacles AT benbernounadiam coveragewithktransmittersinthepresenceofobstacles AT boseprosenjit coveragewithktransmittersinthepresenceofobstacles AT damianmirela coveragewithktransmittersinthepresenceofobstacles AT demaineerikd coveragewithktransmittersinthepresenceofobstacles AT dujmovicvida coveragewithktransmittersinthepresenceofobstacles AT flatlandrobin coveragewithktransmittersinthepresenceofobstacles AT hurtadoferran coveragewithktransmittersinthepresenceofobstacles AT iaconojohn coveragewithktransmittersinthepresenceofobstacles AT lubiwanna coveragewithktransmittersinthepresenceofobstacles AT morinpat coveragewithktransmittersinthepresenceofobstacles AT sacristanvera coveragewithktransmittersinthepresenceofobstacles AT souvainediane coveragewithktransmittersinthepresenceofobstacles AT uehararyuhei coveragewithktransmittersinthepresenceofobstacles |