Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation

Therese Biedl, Timothy M. Chan, Stephanie Lee, Saeed Mehrabi, Fabrizio Montecchiani, Hamideh Vosoughpour, Ziting Yu

Research output: Contribution to journalArticlepeer-review


A sliding k-transmitter inside an orthogonal polygon P, for a fixed k≥ 0 , is a point guard that travels along an axis-parallel line segment s in P. The sliding k-transmitter can see a point p∈ P if the perpendicular from p onto s intersects the boundary of P in at most k points. In the Minimum Sliding k-Transmitters (ST k) problem, the objective is to guard P with the minimum number of sliding k-transmitters. In this paper, we give a constant-factor approximation algorithm for the ST k problem on P for any fixed k≥ 0. Moreover, we show that the ST problem is NP-hard on orthogonal polygons with holes even if only horizontal sliding 0-transmitters are allowed. For k> 0 , the problem is NP-hard even in the extremely restricted case where P is simple and monotone. Finally, we study art gallery theorems; i.e., we give upper and lower bounds on the number of sliding transmitters required to guard P relative to the number of vertices of P.

Original languageEnglish (US)
Pages (from-to)69-97
Number of pages29
Issue number1
StatePublished - Jan 15 2019
Externally publishedYes


  • Art gallery problem
  • Sliding k-transmitters
  • ϵ-nets

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation'. Together they form a unique fingerprint.

Cite this