Line segment visibility with sidedness constraints

Abstract

We study a family of line segment visibility problems, related to classical art gallery problems, which are motivated by monitoring requirements in commercial data centers. Given a collection of non-overlapping line segments in the interior of a rectangle, and a requirement to monitor the segments from one side or the other, we examine the problem of finding a minimal set of point guards. Guards may be placed anywhere in the interior of the rectangle but not on a line segment. We consider combinatorial bounds of problem variants where the problem solver gets to decide which side of the segments to guard or the problem poser gets to decide which side to guard, and many others. We show that virtually all variants are NP-Hard to solve exactly, and then provide heuristics and experimental results to give insight into the associated practical problems. Finally we describe a program for using experiments to guide the search for optimal combinatorial bounds.