Line segment visibility with sidedness constraints (Q2144449)

Motivated by the problem of efficient monitoring of the cooling and heat production in commercial data centres, the authors study a variant of the classical art gallery problem. In the considered variant, we are interested in guarding not the entire polygon but line segments in the polygon's interior. In the paper, the authors consider only rectangular art galleries because most data centres are rectangular or nearly rectangular. Moreover, the authors introduce a family of problems that they call ``all-but-\(\delta\)'' coverage, where we allow to omit some arbitrarily small length \(\delta\) along each segment. The authors present a set of combinatorial bounds giving how many guards are needed to cover \(n\) segments in the worst case. They divide the bounds into three cases: (1) all segments are vertical, (2) segments are axis-aligned, and (3) segments are arbitrarily aligned. Next, the authors prove that even in the simplest guarding models, the problem of finding a minimal guard set is NP-hard and that the same is true for the all-but-\(\delta\) variants. Lastly, the authors focus on developing heuristics that scale to the size of large commercial data centres. In the proposed heuristic, the candidate guards are placed within successively finer grids, and then integer programming is used to find a stable solution. To show the effectiveness of the proposed approach, the authors describe a series of experiments.