License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.11
URN: urn:nbn:de:0030-drops-87246
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8724/
Go to the corresponding LIPIcs Volume Portal

Bonnet, Édouard ; Giannopoulos, Panos

Orthogonal Terrain Guarding is NP-complete

pdf-format:
LIPIcs-SoCG-2018-11.pdf (0.5 MB)

Abstract

A terrain is an x-monotone polygonal curve, i.e., successive vertices have increasing x-coordinates. 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 NP-complete [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 k^{O(k)}n^{O(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 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})} ETH-hardness 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 NP-complete. Then, we show how their reduction from Planar 3-SAT (as well as our adaptation for rectilinear terrains) can actually be made linear (instead of quadratic).

BibTeX - Entry

@InProceedings{bonnet_et_al:LIPIcs:2018:8724,
  author =	{{\'E}douard Bonnet and Panos Giannopoulos},
  title =	{{Orthogonal Terrain Guarding is NP-complete}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8724},
  URN =		{urn:nbn:de:0030-drops-87246},
  doi =		{10.4230/LIPIcs.SoCG.2018.11},
  annote =	{Keywords: terrain guarding, rectilinear terrain, computational complexity}
}

Keywords: terrain guarding, rectilinear terrain, computational complexity
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI