Exact Algorithms for Terrain Guarding

Abstract

Given a 1.5-dimensional terrain T , also known as an x -monotone polygonal chain, the T errain G uarding problem seeks a set of points of minimum size on T that guards all of the points on T . Here, we say that a point p guards a point q if no point of the line segment pq is strictly below T . The T errain G uarding problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm (SODA 2005). However, only in 2010 King and Krohn (SODA 2010) finally showed that T errain G uarding is NP-hard. In spite of the remarkable developments in approximation algorithms for T errain G uarding , next to nothing is known about its parameterized complexity. In particular, the most intriguing open questions in this direction ask whether, if parameterized by the size k of a solution guard set, it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this article, we answer the first question affirmatively by developing an n O (√ k ) -time algorithm for both D iscrete T errain G uarding and C ontinuous T errain G uarding . We also make non-trivial progress with respect to the second question: we show that D iscrete O rthogonal T errain G uarding , a well-studied special case of T errain G uarding , is fixed-parameter tractable.