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 journalArticle

    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)
    Pages (from-to)208-233
    Number of pages26
    JournalJournal of Combinatorial Optimization
    Volume25
    Issue number2
    DOIs
    StatePublished - 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

    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. (2013). Coverage with k-transmitters in the presence of obstacles. Journal of Combinatorial Optimization, 25(2), 208-233. https://doi.org/10.1007/s10878-012-9475-x