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 journalArticlepeer-review


    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
    Issue number2
    StatePublished - Feb 2013


    • 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


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

    Cite this