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 proceedingConference 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 languageEnglish (US)
    Title of host publicationCombinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Proceedings
    Pages1-15
    Number of pages15
    EditionPART 2
    DOIs
    StatePublished - 2010
    Event4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010 - Kailua-Kona, HI, United States
    Duration: Dec 18 2010Dec 20 2010

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    NumberPART 2
    Volume6509 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010
    CountryUnited States
    CityKailua-Kona, HI
    Period12/18/1012/20/10

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Coverage with k-transmitters in the presence of obstacles'. Together they form a unique fingerprint.

  • 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