City Research Online

Abstract

A terrain is an x-monotone polygonal curve, that is, every vertical line crosses the curve at most once. In the Terrain Guarding problem, a special case of the famous art gallery problem, one has to place at most k guards on the vertices of a n-vertex terrain, in order to fully see it. In 2010, King and Krohn showed that Terrain Guarding is NP-hard [SODA '10, SIAM J. Comput. '11] thereby solving a long-standing open question. They observe that their proof does not settle the complexity of Orthogonal Terrain Guarding where the terrain only consists of horizontal or vertical segments; those terrains are called rectilinear or orthogonal. Recently, Ashok et al. [SoCG'17] presented an FPT algorithm running in time kO(k)nO(1) for Dominating Set in the visibility graphs of rectilinear terrains without 180-degree vertices. They ask if Orthogonal Terrain Guarding is in P or NP-hard. In the same paper, they give a subexponential-time algorithm running in nO(n√) (actually even nO(k√)) for the general \tg and notice that the hardness proof of King and Krohn only disproves a running time 2o(n1/4) under the ETH. Hence, there is a significant gap between their 2O(n1/2logn)-algorithm and the no 2o(n1/4) ETH-hardness implied by King and Krohn's result.

In this paper, we adapt the gadgets of King and Krohn to rectilinear terrains in order to prove that even Orthogonal Terrain Guarding is NP-complete. Then, we show how to obtain an improved ETH lower bound of 2Ω(n1/3) by refining the quadratic reduction from Planar 3-SAT into a cubic reduction from 3-SAT. [In the conference version of this paper, we mistakenly claim a tighter lower bound.] This works for both Orthogonal Terrain Guarding and Terrain Guarding.

Publication Type:	Article
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology > Computer Science School of Science & Technology > Computer Science > giCentre

Export

Downloads