Giannopoulos, P. ORCID: 0000000262611961 and Bonnet, E. (2018). Orthogonal Terrain Guarding is NPcomplete. Paper presented at the 34th International Symposium on Computational Geometry (SoCG 2018), 11  14 June 2018, Budapest, Hungary.
Abstract
A terrain is an xmonotone polygonal curve, i.e., successive vertices have increasing xcoordinates. Terrain Guarding can be seen as a special case of the famous art gallery problem where one has to place at most k guards on a terrain made of n vertices in order to fully see it. In 2010, King and Krohn showed that Terrain Guarding is NPcomplete [SODA '10, SIAM J. Comput. '11] thereby solving a longstanding 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 k^{O(k)}n^{O(1)} for Dominating Set in the visibility graphs of rectilinear terrains without 180degree vertices. They ask if Orthogonal Terrain Guarding is in P or NPhard. In the same paper, they give a subexponentialtime algorithm running in n^{O(sqrt n)} (actually even n^{O(sqrt k)}) for the general Terrain Guarding and notice that the hardness proof of King and Krohn only disproves a running time 2^{o(n^{1/4})} under the ETH. Hence, there is a significant gap between their 2^{O(n^{1/2} log n)}algorithm and the no 2^{o(n^{1/4})} ETHhardness implied by King and Krohn's result. In this paper, we answer those two remaining questions. We adapt the gadgets of King and Krohn to rectilinear terrains in order to prove that even Orthogonal Terrain Guarding is NPcomplete. Then, we show how their reduction from Planar 3SAT (as well as our adaptation for rectilinear terrains) can actually be made linear (instead of quadratic).
Publication Type:  Conference or Workshop Item (Paper) 

Additional Information:  © Édouard Bonnet and Panos Giannopoulos; licensed under Creative Commons License CCBY 
Publisher Keywords:  terrain guarding, rectilinear terrain, computational complexity 
Subjects:  Q Science > QA Mathematics > QA75 Electronic computers. Computer science 
Departments:  School of Mathematics, Computer Science & Engineering > Computer Science 
Date Deposited:  08 Feb 2019 10:10 
URI:  https://openaccess.city.ac.uk/id/eprint/21500 

Text
 Published Version
Available under License Creative Commons Attribution. Download (500kB)  Preview 
Export
Downloads
Downloads per month over past year
Actions (login required)
Admin Login 