Polygon guarding with orientation

Our contributions in this paper are three-fold: We first prove that Ω(n) guards are always necessary for △-guarding the interior of a simple polygon having n vertices. Second, we present a O(log⁡copt) factor approximation algorithm for △-guarding polygons with or without holes, when the guards are restricted to vertices of the polygon. Here, copt is the optimal number of guards. Third, we study the problem of △-guarding a set of line segments connecting points on the boundary of the polygon. This is motivated by applications where an object or person of interest can only move along certain paths in the polygon. We present a constant factor approximation algorithm for this problem - one of the few such results for art gallery problems.