A fixed-parameter algorithm for guarding 1.5D terrains

• “the depth of the terrain onion peeling” is introduced as a parameter.
• Tree decomposition of the visibility graph of a 1.5D terrain is constructed and its width is bounded by this parameter.
• “terrain path decomposition” is introduced.
• A dynamic programming algorithm is presented to produce a solution to the 1.5D terrain guarding problem.
• 1.5D terrain guarding problem is fixed-parameter tractable with respect to “the depth of terrain onion peeling”.

A 1.5D terrain is a region on a plane determined by an x-monotone polygonal chain. A set G of points on the terrain is called a guarding set if every point on the terrain is seen by some point in G. In the 1.5D terrain guarding problem we are given a 1.5D terrain and the goal is to find the minimum guarding set for the given input terrain. It is proved that this problem is NP-hard and the only previous theoretical results for this problem involve approximation. In this paper, we turn to fixed-parameter tractability. We present “depth of terrain onion peeling” as a new geometric parameter. Based on this parameter, we give an upper bound for the treewidth of the terrain visibility graph. By presenting a dynamic programming algorithm, we show that the 1.5D terrain guarding problem is fixed-parameter tractable with respect to this parameter.