Guarding Orthogonal Terrains.
Stéphane Durocher, Pak Ching Li, Saeed Mehrabi · 2015
A 1.5-dimensional terrain T with n vertices is an x-monotone polygonal chain in the plane. A point guard p on T guards a point q of T if the line segment connect-ing p to q lies on or above T; p is a vertex guard if it is a vertex of T. In the Optimal Terrain Guarding (OTG) problem on T, the objective is to guard the vertices of T by the minimum number of vertex guards. King and Krohn [9] showed that the OTG problem is NP-hard on arbitrary terrains, and Gibson et al. [6] gave a PTAS for this problem. In this paper, we introduce directed visi-bility in which the visibility is directed only at adjacent vertices. We give an O(n)-time algorithm that solves the OTG problem exactly on orthogonal terrains under directed visibility. 1