Parameter Analysis for Guarding Terrains

Abstract

The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an XP algorithm.

1 Introduction

The (Continuous and Discrete) Terrain Guarding problem is a widely studied problem in Discrete and Computational Geometry. In particular, it is the most well-studied visibility problem except for the classic Art Gallery problem. Formally, a 1.5-dimensional terrain $T=(V,E)$, or terrain for short, is a graph on vertex-set $V=\{v_1,v_2,\ldots ,v_n\}$ where each vertex $v_i$ is associated with a point $(x_i,y_i)$ on the two-dimensional Euclidean plane such that $x_1 \le x_2 \le \cdots \le x_n$, and for any $i\in \{1,2,\ldots ,n-2\}$, having $x_i=x_{i+1}=x_{i+2}$ implies that either $y_i<y_{i+1}<y_{i+2}$ or $y_i>y_{i+1}>y_{i+2}$ (see Fig. 1); the edge-set of this graph is $E=\{\{v_i,v_{i+1}\}: i\in \{1,2,\ldots ,n-1\}\}$. In the two-dimensional Euclidean plane, let $R_1$ be the horizontal ray starting from vertex $v_1 \in V$ towards negative infinity, and $R_2$ be the horizontal ray starting from $v_n \in V$ towards positive infinity. The region bounded by $T\cup R_1 \cup R_2$ and lying on and above T is called the region bounded by the terrain T. Note that the points lying on the terrain include the vertices $v_i \in V$, $1 \le i \le n$, as well as the points that lie on the edges in E. The Continuous Terrain Guarding problem takes as input a terrain and a positive integer k, and the objective is to decide whether one can place guards on at most k points on the terrain such that each point on the terrain is seen by at least one guard. When we say that a point p sees a point q, we mean that the line segment ${\overline{pq}}$ lies in the region bounded by the terrain. Notice that the guards may be placed on points on the terrain that do not belong to V. The Discrete Terrain Guarding problem is defined similarly, with the requirement that the guards must be placed on vertices in V only, as well as that only each vertex in V must be guaranteed to be seen by at least one guard.

Fig. 1

A terrain, where convex vertices are denoted by circles, reflex vertices are denoted by double circles, and edges are denoted by straight line segments. The set of reflex vertices sees all the vertices of the terrain

One of the reasons why the Terrain Guarding problem and its numerous variants are important is because there is a wide variety of applications in the design of communication technologies such as cellular networks and line-of-sight transmission networks for radio broadcasting, as well as in coverage of highways, streets and walls with street lights as well as security cameras and natural terrain border security [3, 14]. In Discrete and Computational Geometry, the problem has its origin in 1995, when an NP-hardness proof was claimed by Chen et al. [7]. This proof was never completed and it took almost 15 years until King and Krohn [20] finally showed that this problem is indeed NP-hard. In between, the problem has received a lot of attention from the viewpoint of approximation algorithms. In 2005, Ben-Moshe et al. [3] obtained the first constant-factor approximation algorithm for Discrete Terrain Guarding. Subsequently, the approximation factor was gradually improved in [8, 13, 19], until a PTAS was proposed by Gibson et al. [16] for Discrete Terrain Guarding. Recently, Friedrichs et al. [14] showed that even the Continuous Terrain Guarding problem admits a PTAS.

A special case of Terrain Guarding that has received notable attention is Orthogonal Terrain Guarding, which was recently shown to be NP-hard [5]. Here, the terrain is orthogonal: for each vertex $v_i$, $2\le i\le n-1$, either both $x_{i-1}=x_i$ and $y_i=y_{i+1}$ or both $y_{i-1}=y_i$ and $x_i=x_{i+1}$. In other words, each edge is either a horizontal line segment or a vertical line segment, and each vertex is incident to at most one horizontal edge and at most one vertical edge (see Fig. 2 for two examples of orthogonal terrains). This problem is of particular interest to the algorithm design community as it provides more structure and therefore more positive results than Terrain Guarding [12, 17, 21, 22]. Although the PTASes designed in [14, 16] clearly work for the Orthogonal Terrain Guarding problem as well, studies on this particular variant of Terrain Guarding bring out interesting structural properties specific to this variant. For instance, in the work of Katz and Roisman [17] a relatively simple 2-approximation algorithm is described for Discrete Orthogonal Terrain Guarding. Recently, Lyu and Üngör [21] improved upon this result by developing a linear-time 2-approximation algorithm for Orthogonal Terrain Guarding. In [12, 22], restricted versions were studied under which Orthogonal Terrain Guarding can be solved in polynomial time.

With a satisfactory landscape of approximation results for Terrain Guarding, the focus shifted to parameterized variants of the problem. In fact, in their landmark paper [20] King and Krohn state that “the biggest remaining question regarding the complexity of Terrain Guarding is whether or not it is FPT”. Khodakarami et al. [18] introduced the parameter “the depth of the onion peeling of a terrain” and showed that Terrain Guarding is FPT with respect to this parameter. In [2], for the solution size k as parameter a subexponential-time algorithm for Terrain Guarding with running time $n^{\mathcal {O}(\sqrt{k})}$ was given in both discrete and continuous domains. In the same paper, an FPT algorithm with running time $k^{\mathcal {O}(k)}\cdot n^{\mathcal {O}(1)}$ was presented for Discrete Orthogonal Terrain Guarding. We remark that a lower bound of $2^{\Omega (\sqrt{n})}$ for the time complexity of any algorithm for Terrain Guarding under the Exponential Time Hypothesis (ETH) was claimed in the conference version [4] of [5], but the proof was said to be false and replaced by a lower bound of $2^{\Omega (n^{1/3})}$ under the ETH in [5].

The Parameters We consider two structural parameters. So far, the understanding of the parameterized complexity of Terrain Guarding has been very limited, and, more generally, exact (exponential-time) algorithms for any visibility problem are extremely scarce. All our results utilize new and known structural properties of terrains. The individual results make use of different methods in parameterized complexity, and thus show several ways of how the aforementioned structural properties can be exploited algorithmically. In particular, we show how the paradigm of parameterized complexity can successfully yield positive, non-trivial results in the context of visibility. We believe that our work will open the door for additional research of which structural properties of terrains, polygons and related input domains make them easy to solve, and which do not. For example, here we see that terrains somewhat close to being convex, or which has constantly many minima, can be efficiently guarded.

We first consider the number r of reflex vertices of the terrain as a parameter; reflex vertices are those whose incident edges create an angle strictly larger than 180 degree in the region bounded by the terrain (see Fig. 1);¹ all other vertices are convex vertices. It is known (and follows from, say, Theorem 1.5 of [23]) that if one places a guard on each of the reflex vertices of the terrain, then all points of the terrain are guarded. Hence, the parameterized instances of interest are those where $r > k$, k being the intended solution size. Thus, r can be considered as a natural relaxation of parameterization by solution size (whose status is a longstanding open problem). Further, we believe that it is interesting in its own right, since having a small (but not necessarily a fixed constant) parameter r means that the terrain is close to being convex. For such terrains, our result (formally stated ahead) not only shows that the problem is solvable efficiently (by a parameterized algorithm) but also that, in fact, the entire terrain can be shrunk to be of small size (by a kernelization algorithm).

We would like to remark that for a closely related problem called Art Gallery, the problem has been studied with respect to the number of reflex vertices, inspired by the W[1]-hardness result of Bonnet and Miltzow [6] for the problem, when parameterized by the number of reflex vertices. In particular, Agrawal et al. [1] obtained that Art Gallery parameterized by the number of reflex vertices admits an FPT algorithm.

Fig. 2

As illustration of c being arbitrary a larger or b smaller than k. In the terrains vertices are denoted by squares and edges by straight line segments. The red vertices are solution vertices, and the blue edges are the minima (Color figure online)

The second structural parameter we consider is the number c of local minima (or minima for short) of the terrain, for orthogonal terrains. Recall that in the orthogonal terrains that we consider, every vertex is incident to at most one horizontal and at most one vertical edge. Then in an orthogonal terrain, a minimum is a horizontal edge whose y-coordinates are all the same as well as smaller than that of the (at most) two neighbours on either end (see the blue edges in Fig. 2). Notice that in an orthogonal terrain, except for possibly the first and the last vertices of the terrain, the minima occur in pairs of convex endpoints of horizontal edges (see Fig. 2).

It is to be noted that c, unlike r, cannot be related to k—it can be arbitrarily smaller or arbitrarily larger than k (as well as than r); see Fig. 2. We believe that in many naturally occurring terrains the number of minima is much smaller than the number of observable vertices (where the gradient of the terrain changes). Indeed, it is conceivable to have (e.g., on natural hills or artificial structures) a huge number of vertices with slight changes of slope, and only few that actually alter the current “trend” (of having increasing y-coordinates or decreasing y-coordinates) of the terrain, in which case c is small.

Our Contribution First, we consider the Discrete Terrain Guarding problem parameterized by the number r of reflex vertices. Then, an instance of the problem is denoted by (T, k, r), where the input terrain T has r reflex vertices, and the objective is to determine if there is a k-sized vertex guard set for guarding all vertices of the terrain. Parameterized by r, we obtain a polynomial kernel for Terrain Guarding:

Theorem 1

For an instance (T, k, r) of Discrete Terrain Guarding, in polynomial time we can find an equivalent instance $(T'=(V',E'),k,r)$ of the problem, where $|V'| \in \mathcal {O}(r^2)$. Moreover, the problem admits a polynomial kernel, when parameterized by r.

Our algorithm exploits structural properties of consecutively appearing convex vertices to identify vertices sufficient to capture a solution. We also find vertices guarding which would imply that all vertices of the terrain are guarded. Then, roughly speaking, we remove useless vertices (and make their neighbors adjacent) to obtain an instance with ${\mathcal {O}}(r^2)$ vertices. We remark that Theorem 1 also works for Continuous Terrain Guarding, by using an appropriate “discretization” as described in [14] (for details see Sect. 3).

We would like to note that the equivalent instance $(T',k'r)$ with $|V'| \in \mathcal {O}(r^2)$, obtained using the first statement in the above theorem does not directly imply a polynomial kernel for the problem, as the coordinates of the vertices of $T'$ may not be bounded by a (polynomial) function of r. Thus to obtain a polynomial kernel using the above instance, we will rely on the known (explicit) polynomial time reducibility among appropriate NP-complete problems.

Next, we consider Discrete Orthogonal Terrain Guarding parameterized by the number of minima, c, of the input orthogonal terrain. We design a somewhat tricky dynamic programming algorithm for it that belongs to XP. The membership in FPT remains open.

Theorem 2

Discrete Orthogonal Terrain Guarding parameterized by c can be solved in $4^c\cdot n^{2c +{\mathcal {O}}(1)}$ time.

2 Preliminaries

For a positive integer k, we use [k] as a shorthand for $\{1,2,\ldots ,k\}$. We use standard notation and terminology from the book of Diestel [10] for graph-related terms which are not explicitly defined here. We only consider simple undirected graphs. Given a graph H, V(H) and E(H) denote its vertex-set and edge-set, respectively.

Terrains Consider a terrain $T=(V,E)$, where $V=\{v_i=(x_i,y_i)\mid i \in [n]\}$ and $x_1\le x_2\le \cdots \le x_n$. We denote the ordering of vertices in T by $v_1\prec v_2 \prec \cdots \prec v_n$. Moreover, for vertices $v_i,v_j\in V$, we write $v_i \prec v_j$ if $i<j$, and $v_i \preceq v_j$ if $i \le j$. We say that a subset of points P on the terrain sees a subset of points Q on the terrain if each point in Q is seen by at least one point in P. A subterrain of T is an induced subgraph of T over a set $\{v_i,v_{i+1},\ldots ,v_j\}$ of consecutive vertices in V with $i \le j \in [n]$ (retaining the points associated with the vertices).

Proposition 1

(Order Claim [3]) For a terrain $T =(V,E)$, consider four vertices $v_i \prec v_j \prec v_t \prec v_r$, such that $v_i$ sees $v_t$, and $v_j$ sees $v_r$. Then, $v_i$ sees $v_r$.

Consider an orthogonal terrain $T=(V,E)$. A minimum (resp. maximum) of T is a pair of consecutive vertices $(v_{i},v_{i+1})$ of T, where $1 \le i \le n$, such that the following conditions are satisfied: i) $y_i = y_{i+1}$, ii) if $v_{i-1}$ exists, then $y_{i-1} > y_i$ (resp. $y_{i-1} < y_i$), and iii) if $v_{i+2}$ exists, then $y_{i+1} < y_{i+2}$ (resp. $y_{i+1} > y_{i+2}$).² We denote the set of minima and maxima of T by $\mathsf{Min}(T)$ and $\mathsf{Max}(T)$, respectively.

Parameterized Complexity In Parameterized Complexity each problem instance is accompanied by a parameter k. A central notion in this field is fixed-parameter tractability (FPT). This means, for a given instance (I, k), solvability in time $f(k)|I|^{\mathcal {O}(1)}$ where f is some computable function of k. A kernelization algorithm for a parameterized problem $\Pi$ is a polynomial time procedure which takes as input an instance (x, k), where k is the parameter, and returns an instance $(x',k')$ such that $(x,k) \in \Pi$ if and only if $(x',k')\in \Pi$ and $|x'| + k' \le g(k)$, where g is a computable function. In the above, we say that $\Pi$ admits a g(k)-kernel. If g(k) is a polynomial function, then the kernel is a polynomial kernel for $\Pi$. For more information on Parameterized Complexity we refer the reader to [9, 11].

3 Polynomial Kernel for Discrete Terrain Guarding

We design a polynomial kernel for Discrete Terrain Guarding when parameterized by the number of reflex vertices. The main goal will be to prove the next lemma, which is the first statement of Theorem 1.

Lemma 1

For an instance (T, k, r) of Discrete Terrain Guarding, in polynomial time we can compute an equivalent instance $(T' = (V',E'),k,r)$ of the problem, where $|V'| \in {\mathcal {O}}(r^2)$.

We (again) remark that the above lemma does not direct imply a polynomial kernel for Discrete Terrain Guarding as it may not necessarily be possible to represent the coordinates of points in the resulting instance using bit-length proportional to a (polynomial) function of r. Thus to obtain a proof of Theorem 1, after proving Lemma 1, we will rely on (an explicit) two-step polynomial time reduction via the Dominating Set problem, exploiting the polynomial time reducibility among NP-complete problems, to obtain a proof of the theorem.

Now we focus on the proof of Lemma 1. Let $(T=(V,E),k,r)$ be an instance of Discrete Terrain Guarding. We will design three marking schemes that will mark at most $\mathcal {O}(r^2)$ vertices. Roughly speaking, we will argue that there is a solution contained in the marked set of vertices, and guarding the marked vertices is enough to guard all the vertices. Our first marking scheme will be used to ensure that there is a solution that contains only marked vertices. Our second and third marking schemes will be used to ensure that it is enough to guard the marked vertices. Finally, to obtain the proof of Lemma 1, we construct a modified terrain by adding edges between “consecutive” marked vertices in the original terrain. We begin with some definitions and establish some useful properties regarding them, which will be helpful in proving the lemma.

Fig. 3

An illustration of convex regions in a terrain and Marking Scheme II. The terrain has six convex regions $C_1,C_2,\ldots ,C_6$, and the reflex vertices are double circled. The blue/red/green (dotted) lines/points/squares are the objects defined in Marking Scheme II. Also, the labelling of vertices and points are as defined in Marking Scheme II. We remark that for the pair of reflex vertices $w,w'$, the line segment ${\overline{L}}_{ww'}$ is blocked by the terrain (Color figure online)

For a terrain $T'$, a convex region of $T'$ is a maximal subterrain of $T'$ where every vertex is a convex vertex (see Fig. 3). For a convex region C, the vertex set of C is denoted by V(C). A vertex in V(C) that is not one of the two (not necessarily distinct) endpoints is called an internal vertex of C. A partial convex region is a subterrain of a convex region C that contains at least one endpoint of C. We can also define internal vertices of partial convex regions as above. Notice that the ordering of vertices given by $\preceq$ (and $\prec$) naturally extends to an ordering of convex regions, as two convex regions do not have common vertices. Thus, hereafter we will use $\preceq$ (and $\prec$) to denote orderings among convex regions as well. In the following we state some useful observations regarding convex regions. The next observation follows from from the assumption that the end vertices of a terrain are reflex vertices.

Observation 3

The number of convex regions in T is at most $r-1$.

Observation 4

Consider a convex region C in T with endpoints $v_i \preceq v_j$. For each $u,u' \in V(C) \cup \{v_{i-1}, v_{j+1}\}$,³u sees $u'$.

Observation 5

Let C be a convex region in T with endpoints $v_i\preceq v_j$. Consider vertices $v \notin V(C)$ and $u \in V(C)$, such that v sees u and $v \preceq v_i \preceq u \preceq v_j$ (resp. $v_i \preceq u \preceq v_j \preceq v$). Then v sees each vertex $u'$ such that $u \preceq u' \preceq v_j$ (resp. $v_i \preceq u' \preceq u$).

Proof

Consider the case when $v \preceq v_i \preceq u \preceq v_j$. (The other case can be proved by following similar arguments.) If $u=v_j$, then the claim trivially follows. Thus we assume that $u \prec v_j$. Consider $u'\in V(C)$, such that $u \prec u' \preceq v_j$. If $v = v_{i-1}$, then from Observation 4 it follows that v sees $u'$. Now we consider the case when $v \prec v_{i-1}$. From Observation 4, $v_{i-1}$ sees $u'$, by our assumption v sees u, and we have $v \prec v_{i-1} \prec u \prec u'$. Thus by the Order Claim (Proposition 1) we can conclude that v sees $u'$. $\square$

We are now ready to state our first marking scheme. Intuitively speaking, this marking scheme is used to identify a set of vertices where we can always find a solution.

Definition 1

(Marking Scheme I) We create a subset $S_1 \subseteq V$ of vertices as follows.

• 1. Add all the reflex vertices of T to $S_1$.

• 2. For each convex region C, add its two (not necessarily distinct) endpoints to $S_1$.

• 3. Consider an ordered pair of distinct convex regions $(C_i,C_j)$ such that there is $v \in V(C_i)$ that sees all vertices of $C_j$. If $C_i \prec C_j$ (resp. $C_j \prec C_i$), let $f(C_i,C_j)$ be the largest (resp. smallest) vertex in $C_i$ other than the endpoints of $C_i$ that sees $C_j$. Add $f(C_i,C_j)$ to $S_1$.

• 4. Consider a reflex vertex v and a convex region C with endpoints $v_i,v_j$, such that $v_i \preceq v_j \prec v$ (resp. $v \prec v_i \preceq v_j$). Let f(C, v) be the largest (resp. smallest) vertex in C, other than the endpoints of C, that v sees. Add f(C, v) to $S_1$.

The following observation easily follows from the above definition and Observation 3.

Observation 6

The number of vertices in $S_1$ is bounded by $\mathcal {O}(r^2)$.

In the next lemma we show existence of a solution (for a yes-instance) contained in $S_1$.

Lemma 2

(T, k, r) is a yes-instance of Discrete Terrain Guarding if and only if there is a solution $S' \subseteq S_1$.

Proof

If some $S' \subseteq S_1$ is a solution for (T, k, r) then (T, k, r) is a yes-instance. Now suppose that (T, k, r) is a yes-instance. Consider a solution $S'$ for (T, k, r) that maximizes the number of vertices from $S_1$ and is of minimum possible size. If $S'\subseteq S_1$, then we are done. Thus, we assume that there is $v \in S' {\setminus } S_1$. From Item 1 and 2 of Definition 1 we can obtain that v is neither a reflex vertex nor an endpoint of any convex region in T. Thus we assume that v belongs to a convex region, say C, with $v_i\prec v_j$ as its endpoints.

We first consider the case when there is a convex region $\widetilde{C}$ such that: i) $\widetilde{C}$ contains a vertex that is seen by v and no vertex in $S'{\setminus } \{v\}$, and ii) v does not see all vertices of $\widetilde{C}$. (Note that $\widetilde{C} \ne C$, from Observation 4.) Without loss of generality we assume that $\widetilde{C} \prec C$. (The other case can be argued symmetrically.) For the arguments that follow, please refer to Fig. 4a. Let $v_{{\tilde{i}}} \prec v_{{\tilde{j}}}$ be the endpoints of $\widetilde{C}$. We will argue that $S^* = (S'{\setminus } \{v\}) \cup \{v_j\}$ is a solution for (T, k, r). Clearly, $|S^*| \le k$. We will now argue that $S^*$ sees each vertex in V. To prove the above, it is enough to show that for each $u \in V$, such that v is the only vertex in $S'$ that sees it, either $v_j$ sees u, or we arrive at a contradiction to our assumption that v is the only vertex in $S'$ that sees u. Consider such a vertex u, and the following cases based on the position of u.

• If $u \in V(C)$, then from Observation 4, $v_j$ sees u.

• Now we consider the case when $u \prec v_i \prec v \prec v_j$. We will show that $v_j$ sees u, or arrive at a contradiction that u is seen only by v in $S'$. Recall that u sees v by our assumption and $v_i$ sees $v_j$ (Observation 4). Thus using the Order Claim (Proposition 1) on $u \prec v_i \prec v \prec v_j$, we conclude that $v_j$ sees u.

• Finally, we consider the case when $v_i \prec v \prec v_j \prec u$. As v does not see all vertices of $\widetilde{C}$ and $\widetilde{C} \prec C$, using Observation 5 we conclude that v does not see $v_{{\tilde{j}}}$. As $S'$ is a solution, there is some $\widehat{u}\in S'{\setminus } \{v\}$ that sees $v_{{\tilde{j}}}$. By Observations 4 and 5, respectively, if $\widehat{u} \in V(\widetilde{C})$ or $v_{{\tilde{j}}} \prec \widehat{u}$ then $\widehat{u}$ sees all vertices in $\widetilde{C}$, which contradicts the choice of $\widetilde{C}$ to contain a vertex seen only by v and no other vertex in $S'$. Thus including the fact that $\widetilde{C} \prec C$, it must be the case that $\widehat{u} \prec v_{{\tilde{i}}} \prec v_{{\tilde{j}}} \prec v_i \prec v \prec v_j \prec u$. From Observation 5 we obtain that v sees $v_{{\tilde{i}}}$, and by assumption $\widehat{u}$ sees $v_{{\tilde{j}}}$. Thus, using the Order Claim for vertices $\widehat{u} \prec v_{{\tilde{i}}} \prec v_{{\tilde{j}}} \prec v$, we obtain that $\widehat{u}$ sees v. Next, as $\widehat{u} \prec v_{i} \prec v \prec v_{j}$, $\widehat{u}$ sees v, and $v_{i}$ sees $v_{j}$ (Observation 4 applied to C), using the Order Claim on $\widehat{u} \prec v_{i} \prec v \prec v_{j}$ we obtain that $\widehat{u}$ sees $v_{j}$. Finally as $\widehat{u} \prec v \prec v_{j} \prec u$, v sees u, and $\widehat{u}$ sees $v_{j}$, using the Order Claim on $\widehat{u} \prec v \prec v_{j} \prec u$ we obtain that $\widehat{u}$ sees u. The above contradicts that v is the only vertex in $S'$ that sees u. From the above discussion we can conclude that $S^* = (S' {\setminus } \{v\}) \cup \{v_j\}$ is a solution for the instance (T, k, r), such that either $|S^*| < |S'|$, or $|S^*| = |S'|$ and $|S^* \cap S_1| > |S' \cap S_1|$. This contradicts the choice of $S'$.

Hereafter we assume that for any convex region $\widetilde{C}$, either v sees all the vertices in $\widetilde{C}$ or sees none of its vertices. Again our goal will be to find another solution $S^*$ by modifying $S'$ so as to obtain a contradiction to the choice of $S'$. Towards the construction of $S^*$, we start by constructing a set X as follows. For each reflex vertex $u \in V$ such that v is the only vertex in $S'$ that sees u, we add the vertex f(C, u) to X (see Definition 1). Similarly, for each convex region $C'$ such that v is the only vertex in $S'$ that sees all the vertices of it, add the vertex $f(C,C')$ to X. As $S'$ is a minimum sized solution, and hence a minimal solution, and $v\notin S_1$, we obtain that $X\ne \emptyset$. Let $v^* \in X$ be a vertex that is closest to v in (the path in) C. We assume that $v_i \preceq v \prec v^* \prec v_j$. (The case when $v_i \prec v^* \prec v \preceq v_j$ can be argued symmetrically.) For the arguments that follow, please refer to Fig. 4b. Let $S^* = (S'{\setminus } \{v\})\cup \{v^*\}$. Notice that either $|S^*| < |S'|$, or $|S^*| = |S'|$ and $|S^* \cap S_1| > |S' \cap S_1|$. Thus, like previously, if we argue that $S^*$ is a solution to (T, k, r), then we will arrive at a contradiction to the choice of $S'$. Now we will show that $S^*$ is a solution for (T, k, r). First, we show that for each reflex vertex that v sees, the vertex $v^*$ sees it as well. Consider a reflex vertex u that is seen by v. If $v^* = f(C,u)$, then clearly, $v^*$ sees u. Now we assume that $v^* \ne f(C,u)$. If $v_i \prec v \prec v_j \prec u$, then by definition of f(C, u) and the fact that $v^* \ne f(C,u)$ we obtain that $v^* \prec f(C,u) \prec v_j \prec u$. As $v^*$ sees $v_j$ (Observation 4) and f(C, u) sees u, using the Order Claim on $v^* \prec f(C,u) \prec v_j \prec u$ we can obtain that $v^*$ sees u. Next consider the case when $u \prec v_i \prec v \prec v_j$ (also we have $v^* \ne f(C,u)$ and $v \prec v^*$). In this case by definition of f(C, u) and the fact that $v \notin S_1$, we obtain that $u \prec f(C,u) \prec v \prec v^*$. As v sees u and f(C, u) sees $v^*$, we apply the Order Claim on $u \prec f(C,u) \prec v \prec v^*$ to obtain that $v^*$ sees u.

Next, we show that for each convex region $\widetilde{C}$ that v sees (we are in the case when v sees all vertices of a convex region or none), the vertex $v^*$ sees it as well. If $v^* = f(C,\widetilde{C})$, then clearly, $v^*$ sees $\widetilde{C}$. Now we assume that $v^* \ne f(C,\widetilde{C})$. If $C \prec \widetilde{C}$ then $v_i \prec v \prec v_j \prec u$ for each vertex $u \in V(\widetilde{C})$. Then by definition of $f(C,\widetilde{C})$ and the fact that $v^* \ne f(C,\widetilde{C})$ we obtain that $v^* \prec f(C,\widetilde{C}) \prec v_j \prec u$ for each vertex $u \in \widetilde{C}$. As $v^*$ sees $v_j$ (Observation 4) and $f(C,\widetilde{C})$ sees $\widetilde{C}$, using the Order Claim on $v^* \prec f(C,\widetilde{C}) \prec v_j \prec u$ for each vertex $u \in V(\widetilde{C})$, we can obtain that $v^*$ sees each $u \in V(\widetilde{C})$. Next consider the case when $\widetilde{C} \prec C$. Then for each $u \in V(\widetilde{C})$, $u \prec v_i \prec v \prec v_j$ (also we have $v^* \ne f(C,\widetilde{C})$ and $v \prec v^*$). In this case by definition of $f(C,\widetilde{C})$ and the fact that $v \notin S_1$, we obtain that for each $u \in V(\widetilde{C})$, $u \prec f(C,u) \prec v \prec v^*$. As v sees u and $f(C,\widetilde{C})$ sees $v^*$, we apply the Order Claim on $u \prec f(C,u) \prec v \prec v^*$ to obtain that $v^*$ sees u, for each $u \in V(\widetilde{C})$. Thus, $v^*$ sees $\widetilde{C}$. This concludes the proof. $\square$

Fig. 4

An illustrative example of the case study in Lemma 2. Here, v is an unmarked vertex in $S'$ that belongs to convex region C and $v_{i}$, $v_{j}$ are the endpoints of the convex region C. a ${\widetilde{C}}$ is a convex region with endpoints $v_{{\tilde{i}}}$ and $v_{{\tilde{j}}}$. A partial convex region $C'$ of ${\widetilde{C}}$ that includes $v_{{\tilde{i}}}$ is seen by v. The other endpoint $v_{{\tilde{j}}}$ is seen by a vertex ${\widehat{u}}$. b Any convex region that has some vertex seen by v has all its vertices seen by v. The vertex $v^*$ is as defined in Lemma 2. Given a reflex vertex u, the vertex f(C, u) is shown in the diagram

Our next two marking schemes will help us identify vertices such that guarding them will be sufficient for any vertex subset to qualify as a solution. We remark that the ordering $\prec$ (and $\preceq$) of vertices of T naturally extends to the points that lie on the terrain. We will slightly abuse the notation and use $\prec$ (and $\preceq$) to also denote the ordering of points on T.

Definition 2

(Marking Scheme II) Consider an (unordered) pair of distinct reflex vertices $u,u'$ and let $L_{uu'}$ be the line containing them (see Fig. 3). Let ${\overline{L}}_{uu'}$ (if it exists) be the maximal line segment with (possibly non-vertex) endpoints $p_{uu'}$ and $\widehat{p}_{uu'}$ that contains both u and $u'$, and is completely contained on or above T. Let $g^\mathsf{lft}_{uu'}$ and $g^\mathsf{rht}_{uu'}$ be the (not necessarily distinct from $p_{uu'}$) vertices in V such that $g^\mathsf{lft}_{uu'}$ (resp. $g^\mathsf{rht}_{uu'}$) is the largest (resp. smallest) vertex in V, such that $g^\mathsf{lft}_{uu'} \preceq p_{uu'}$ (resp. $p_{uu'} \preceq g^\mathsf{rht}_{uu'}$). Add the vertices $g^\mathsf{lft}_{uu'}$ and $g^\mathsf{rht}_{uu'}$, and their (at most two) neighbors in T to $S_2$. Similarly, let $\widehat{g}^\mathsf{lft}_{uu'}$ (resp. $\widehat{g}^\mathsf{rht}_{uu'}$) be the largest (resp. smallest) vertex in V, such that $\widehat{g}^\mathsf{lft}_{uu'} \preceq \widehat{p}_{uu'}$ (resp. $\widehat{p}_{uu'} \preceq \widehat{g}^\mathsf{rht}_{uu'}$). Add the vertices $\widehat{g}^\mathsf{lft}_{uu'}$ and $\widehat{g}^\mathsf{rht}_{uu'}$, and their neighbors in T to $S_2$.

We design another simple marking scheme, which constructs a set of vertices $S_3$ which marks the neighbors of the vertices in $S_1\cup S_2$ (excluding vertices in $S_1\cup S_2$).

Definition 3

(Marking Scheme III) For each $u\in S_1 \cup S_2$ and $v\in V {\setminus } (S_1\cup S_2)$, such that $\{u,v\} \in E$, add the vertex v to $S_3$.

Observation 7

$|S_1 \cup S_2 \cup S_3|$ is bounded by $\mathcal {O}(r^2)$. Moreover, $S_3 \cap (S_1\cup S_2) = \emptyset$.

In the next lemma we show that guarding $S_1\cup S_2\cup S_3$ is enough to guard T, and the guards can be selected from the set $S_1 \cup S_2 \cup S_3$. (Although there is a solution contained in $S_1$ from Lemma 2, we state the lemma a bit differently to simplify its usage later.)

Lemma 3

A set $S'\subseteq S_1\cup S_2 \cup S_3$ of size at most k is a solution for the instance (T, k, r) of Discrete Terrain Guarding if and only if for each $u\in S_1\cup S_2 \cup S_3$, there is some $v\in S'$ that sees u.

Proof

In one direction, suppose there is $S'\subseteq S_1\cup S_2 \cup S_3$ that is a solution for the instance (T, k, r). Then, clearly, for each $u\in S_1\cup S_2 \cup S_3$, there is some $v\in S'$ that sees u.

In the other direction, consider a set $S' \subseteq S_1 \cup S_2 \cup S_3$ of minimum size that sees each vertex in $S_1\cup S_2 \cup S_3$, and $S'$ maximizes the number of reflex vertices it contains. We will show that $S'$ is a solution for the instance (T, k, r). For the sake of contradiction, suppose that there is a vertex $v \in V{\setminus } (S_1 \cup S_2 \cup S_3)$ that is seen by no vertex in $S'$. Since $S_1$ contains all reflex vertices (see Definition 1) and $S_1$ is guarded by $S'$, v must be a convex vertex. Let C be the convex region in T containing v. Let $v'_1 \in S_1\cup S_2 \cup S_3$ be the largest vertex such that $v'_1 \prec v$. Similarly, let $v'_2 \in S_1\cup S_2 \cup S_3$ be the smallest vertex such that $v \prec v'_2$. From Item 2 of Definition 1, both $v'_1$ and $v'_2$ exist, and they must belong to the convex region C. Moreover, from Definition 3, we obtain that $v'_1,v'_2 \in S_3$ (recall that $S_3 \cap (S_1\cup S_2) = \emptyset$, see Observation 7).

If there is a $u_1 \in S'$ such that $u_1 \preceq v'_1$ and $u_1$ sees $v'_1$, then using Observations 4 and 5 we conclude that $u_1$ sees v. Similarly, if there is $u_2\in S'$, such that $v'_2 \preceq u_2$ and $u_2$ sees $v'_2$, then we conclude that $u_2$ sees v. From the above, we assume that there are vertices $u_1,u_2 \in S'$, such that $u_2 \prec v'_1 \prec v \prec v'_2 \prec u_1$, $u_1$ sees $v'_1$, and $u_2$ sees $v'_2$. We now consider the following cases based on whether or not $u_1$ is a reflex vertex.

• 1. Suppose $u_1$ is a reflex vertex (see Fig. 5a). Since $u_1$ sees $v'_1$ but not v, there must be a reflex vertex u, such that $v\prec u \prec u_1$ and the line segment $L_{u_1u}$ intersects the subterrain $C'$ of C between $v'_1$ and v (containing these vertices). Hence $C'$ must contain a vertex from $S_2$. As $v'_1$ is the largest vertex from $S_1\cup S_2\cup S_3$ with $v'_1\prec v$, $C'$ has no vertex from $S_1\cup S_2\cup S_3$ other than $v'_1$. But $v'_1 \in S_3$ and $S_3\cap (S_1\cup S_2) =\emptyset$. This leads to a contradiction.

• 2. Suppose $u_1$ belongs to a convex region, say $C'$. By our assumption $u_1$ does not see v, thus using Observation 4 we obtain that $C' \ne C$. Moreover, as $v \prec u_1$, we have $C \prec C'$. Let $u_\mathsf{rht}$ be the smallest reflex vertex such that $u_1 \prec u_\mathsf{rht}$, and $u_\mathsf{lft}$ be the largest reflex vertex such that $u_\mathsf{lft} \prec u_1$. Note that $u_\mathsf{lft} \prec u_1 \prec u_\mathsf{rht}$. We will show that $S^* = (S' {\setminus } \{u_1\}) \cup \{u_\mathsf{rht}\}$ sees each vertex in $S_1\cup S_2\cup S_3$. Moreover, either $|S^*| < |S'|$, or $|S^*| = |S'|$ and $S^*$ contains strictly more reflex vertices that $S'$. The above would lead us to a contradiction to the choice of $S'$. Now we focus on showing that $S^*$ sees each vertex in $S_1\cup S_2\cup S_3$ (see Fig. 5b). Consider any $u' \in S_1\cup S_2\cup S_3$. If $u'$ is seen by a vertex in $S' {\setminus } \{u_1\}$, then clearly, $S^*$ sees $u'$. If $u'\in V(C')$ or $u' \in \{u_\mathsf{lft}, u_\mathsf{rht}\}$, then using Observation 4 we can obtain that $u_\mathsf{rht}$ sees $u'$. Now we can assume that either $u' \prec u_\mathsf{lft}$ or $u_\mathsf{rht} \prec u'$. First consider the case when $u' \prec u_\mathsf{lft}$. As $u' \prec u_\mathsf{lft} \prec u_1 \prec u_\mathsf{rht}$, $u_1$ sees $u'$ (by assumption), and $u_\mathsf{lft}$ sees $u_\mathsf{rht}$ (Observation 4), using the Order Claim on $u' \prec u_\mathsf{lft} \prec u_1 \prec u_\mathsf{rht}$ we obtain that $u_\mathsf{rht}$ sees $u'$. Now we consider the other case, i.e., when $u_\mathsf{rht} \prec u'$. Recall that $u_2 \prec v'_1 \prec v'_2 \prec u_1$, and $u_1$ sees $v'_1$ and $u_2$ sees $v'_2$. Thus using the Order Claim on $u_2 \prec v'_1 \prec v'_2 \prec u_1$ we obtain that $u_1$ sees $u_2$. As $u_2 \prec u_\mathsf{lft} \prec u_1 \prec u_\mathsf{rht}$, $u_1$ sees $u_2$, and $u_\mathsf{lft}$ sees $u_\mathsf{rht}$, using the Order Claim on $u_2 \prec u_\mathsf{lft} \prec u_1 \prec u_\mathsf{rht}$ we obtain that $u_2$ sees $u_\mathsf{rht}$. Again, as $u_2 \prec u_1 \prec u_\mathsf{rht} \prec u'$, $u_2$ sees $u_\mathsf{rht}$, and $u_1$ sees $u'$, using the Order Claim on $u_2 \prec u_1 \prec u_\mathsf{rht} \prec u'$ we obtain that $u_2$ sees $u'$. This concludes the proof.

$\square$

Fig. 5

An illustrative example of the case study in Lemma 3. Here, $v_1'$ and $v_2'$ are the nearest marked vertices to v. The vertices $v_1'$ and $v_2'$ are seen by $u_1$ and $u_2$, respectively. a In Case 1, $u_1$ is a reflex vertex that sees $v_1'$ but cannot see v because of a reflex vertex u. b In Case 2, $u_1$ is a convex vertex and $u_\mathsf{rht}$ is the smallest reflex vertex to the right of $u_1$. Similarly, $u_\mathsf{lft}$ is the largest reflex vertex to the left of $u_1$

We define a new terrain $T' = (V' = S_1 \cup S_2 \cup S_3, E')$ (see Fig. 6), where the coordinates of $S_1 \cup S_2 \cup S_3$ remain the same as in T and the edge set $E'$ is defined as follows. Consider the restriction of the ordering, $\prec$, of vertices in T to the vertices in $S_1 \cup S_2 \cup S_3$. The set $E'$ contains an edge between every consecutive pair of vertices in $S_1 \cup S_2 \cup S_3$, given by the above ordering. We have the following observations about the new terrain $T'$.

Fig. 6

An illustrative example of deriving from terrain $T=(V,E)$ shown in a the new terrain $T' = (S_1 \cup S_2 \cup S_3,E')$ shown in b. The vertices in $S_1 \cup S_2 \cup S_3$ are denoted by boxes whereas unmarked vertices of V are denoted as circles

Observation 8

A vertex is reflex in T if and only if it is a reflex vertex in $T'$.

Proof

Consider a reflex vertex v in T. By Definition 1, $v \in V'$. We show that v is also a reflex vertex of $T'$. If v is the first or last vertex of T, then it is also the first or last vertex of $T'$ and therefore is a reflex vertex by definition. Otherwise, v has two neighbours, say $u_1$ and $u_2$. From Definition 1 we can obtain that $u_1,u_2 \in V'$. As the coordinates of $u_1,v,u_2$ in T are the same as that in $T'$, we obtain that v is a reflex vertex of $T'$.

Now we show that a vertex $v\in S_1\cup S_2 \cup S_3$ that is a convex vertex in T is also a convex vertex in $T'$. By definition, v cannot be the first or last vertex. Let $u_1$ and $u_2$ be the two neighbours of v such that $u_1 \prec v \prec u_2$. If $u_1,u_2 \in V'$, then as the coordinates of $u_1,v,u_2$ in T are the same as that in $T'$, we obtain that v is also a convex vertex in $T'$. Otherwise, let $u_1'\in V'$ be the closest such vertex to v where $u_1' \prec v$. By definition of $V'$, such a vertex exists for all convex vertices v. Notice that it must hold that $u_1' \preceq u_1 \prec v$. Also by definition of $V'$, if $u_1$ is a reflex vertex then $u_1' = u_1$ and $u_1 \in V'$. Similarly, let $u_2' \in V'$ be the closest such vertex to v where $v \prec u_2'$. By definition of $V'$, such a vertex exists for all convex vertices v. Notice that it must hold that $v \prec u_2 \preceq u_2'$. Again by definition of $V'$, if $u_2$ is a reflex vertex then $u_2' = u_2$ and $u_2 \in V'$. Note that in $T'$, $u_1'$ and $u_2'$ are the neighbours of v such that $u_1' \prec v \prec u_2'$. We are in the case that at least one of $u_1 \ne u_1'$ and $u_2 \ne u_2'$ holds. If $u_1'$ ($u_2'$) is not a reflex vertex, by construction of $V'$ it must belong to the same convex region as $v,u_1$ ($v,u_2$). By Observation 4, $u_1'$ sees v ($u_2'$ sees v) and therefore $u_1$ lies below or on the line $\widehat{L}_{u_1'v}$ ($u_2$ lies below or on the line $\widehat{L}_{vu_2'}$). Now consider $\angle u_1'vu_2'$ and $\angle u_1vu_2$ made inside the region bounded by T. It must be the case that $\angle u_1'vu_2' \le \angle u_1vu_2$. Thus, if v was a convex vertex in T then it means that in the region bounded by T $\angle u_1vu_2 \le 180^{\circ }$. This implies that in the region bounded by $T'$ $\angle u_1'vu_2' \le 180^{\circ }$, which means that v is a convex vertex of $T'$. $\square$

Observation 9

Given two vertices $u,v \in S_1 \cup S_2 \cup S_3$, u sees v in T if and only if it sees v in $T'$.

Proof

For any $u,v\in S_1 \cup S_2 \cup S_3$ such the u sees v in T, each $w\in V$, such that $v \prec w \prec u$ (or $u \prec w \prec v$) must lie below or on the line $\widehat{L}_{uv}$, containing u and v. In particular, each $w\in S_1 \cup S_2 \cup S_3$ such that $v \prec w \prec u$ (or $u \prec w \prec v$) must lie below or on the line $\widehat{L}_{uv}$. Thus we can obtain that u sees v in $T'$.

Consider $u,v\in S_1 \cup S_2 \cup S_3$ such the u sees v in $T'$. Consider a $w\in V$ such that $u \prec w \prec v$ (we can give a symmetric argument for $v \prec w \prec u$). If $w \in V'$ then it must lie below or on the line $\widehat{L}_{uv}$. Otherwise, $w \in V {\setminus } V'$ and by construction of $V'$, w must be a convex vertex. Let $u_1\in V'$ be the closest such vertex to w such that $u_1 \prec w$ in T. Similarly, let $u_2 \in V'$ be the closest such vertex to w such that $w \prec u_2$ in T. Note that u, v are potential candidates for $u_1$ and $u_2$, respectively and that $u \preceq u_1 \prec u_2 \preceq v$ in $T'$. By definition of $V'$, $u_1,w,u_2$ all belong to a convex region C of T. By Observation 4, $u_1$ sees $u_2$ in T. Since $u_1 \prec w \prec u_2$, w lies below or on the line $\widehat{L}_{u_1u_2}$. Coming back to the fact that u sees v in $T'$ and $u \preceq u_1 \prec u_2 \preceq v$, the line segment $\widehat{L}_{u_1u_2}$ must lie below or on the line segment $\widehat{L}_{uv}$. Putting everything together, we see that w lies below or on the line segment $\widehat{L}_{uv}$. Thus, u sees v in T. $\square$

We are now ready to prove Lemma 1.

Proof of Lemma 1

We show that $(T=(V,E),k,r)$ is a yes-instance of Discrete Terrain Guarding if and only if $(T'=(V',E'),k,r)$ is a yes-instance of the problem. By Observation 8, the reflex vertices of T are reflex vertices of $T'$ and vice versa. Therefore, the number of reflex vertices in both T and $T'$ is r.

First, let (T, k, r) be a yes-instance of Discrete Terrain Guarding. Following from Lemma 2, there is a solution $S' \subseteq S_1\cup S_2\cup S_3$ of size at most k. In particular, $S'$ guards all vertices in $S_1 \cup S_2 \cup S_3$. By Observation 9, $S'$ is a k-sized solution for $(T',k,r)$ and therefore $(T' ,k,r)$ is a yes-instance.

On the other hand, let $(T',k,r)$ be a yes-instance of Discrete Terrain Guarding. Let $S'$ be a k-sized solution for $(T',k,r)$. By Observation 9, $S'\subseteq S_1\cup S_2 \cup S_3$ sees all vertices in $S_1 \cup S_2 \cup S_3$ in the terrain T. Thus, by Lemma 3$S'$ is a solution for (T, k, r) and therefore (T, k, r) is a yes-instance.

Moreover, we can construct $(T',k,r)$ in polynomial time. Also from Observation 7 we have $|V'| \in {\mathcal {O}}(k^2)$. This concludes the proof. $\square$

We are now ready to prove Theorem 1.

Proof of Theorem 1

Let (T, k, r) be an instance of Discrete Terrain Guarding. Using Lemma 1, in polynomial time we compute an equivalent instance $(T'=V',E'),k,r)$ of Discrete Terrain Guarding with $|V'| \in {\mathcal {O}}(r^2)$.

We now construct an instance of Dominating Set (G, k) as follows. We let $V(G) = V'$, and for $u,v\in V(G)$, $\{u,v\} \in E(G)$ if and only if u and v see each other in $T'$. Clearly, (G, k) is a yes-instance of Dominating Set if and only if $(T',k,r)$ is a yes-instance of Discrete Terrain Guarding. Moreover, (G, k) can be constructed in polynomial time. Now we can convert the instance (G, k) of Dominating Set in polynomial time to an equivalent instance of Discrete Terrain Guarding using the NP-hardness reduction from Dominating Set to Discrete Terrain Guarding. (This can be explicitly achieved for example, by a chain of polynomial time reductions Dominating Set $\le _\mathsf{poly}$ SAT $\le _\mathsf{poly}$ 3-SAT $\le _\mathsf{poly}$ Planar 3-SAT $\le _\mathsf{poly}$ Discrete Terrain Guarding [5, 15, 20].) This concludes the proof. $\square$

Remark Regarding Continuous Terrain Guarding We end this section with a note regarding extension of Theorem 1 for Continuous Terrain Guarding. Consider an instance $(\widehat{T}, k,r)$ of Continuous Terrain Guarding, where r is the number of reflex vertices in T. Using the discretization result of Friedrichs et al. (Section 2, [14]), in polynomial time we can construct a terrain $T =(V,E)$ by sub-dividing (possibly multiple times) edges of $\widehat{T}$, and sets X, Y, where $\widehat{V} \subseteq X \subseteq Y \subseteq V$, such that the following condition is satisfied: (T, k, r) is a yes-instance of Continuous Terrain Guarding if and only if there is a set $S\subseteq X$ of size at most k that sees each vertex in Y. Equipped with the above result, we can adapt our marking schemes to consider only vertices from Y while dealing with visibilities, and marking only vertices from X for potential guard set. Using this we can obtain an instance of a restricted (NP-complete) version of Discrete Terrain Guarding with ${\mathcal {O}}(r^2)$ vertices in the terrain. Also by using NP-hardness of Continuous Terrain Guarding, we can obtain a polynomial kernel for the problem.

4 Algorithm for Discrete Orthogonal Terrain Guarding

We design a dynamic programming based algorithm for Discrete Orthogonal Terrain Guarding running in time $4^{|\mathsf{Min}(T)|}\cdot n^{2|\mathsf{Min}(T)|+{\mathcal {O}}(1)}$, where n is the number of vertices in the input orthogonal terrain. Let (T, k) be an instance of Discrete Orthogonal Terrain Guarding. Intuitively speaking, in our algorithm the states for our dynamic programming table are chosen in relation to the minima of T as follows (see Fig. 8). We will maintain a height, on or above which we can place guards. With respect to our minima, we will define the notion of valleys. For each such “valley”, we will have a vertex on its “left slope” in our state of the table, and we would like to guard all the vertices of the valley that appear in the “left slope” and lie on or above this vertex. Similarly, we will have such vertices for the “right slopes”. Towards formalizing the above, we begin by introducing some notations and preliminary results that will be useful later.

Notations We let ${\mathscr {R}}$ and ${\mathscr {C}}$ denote the set of reflex and convex vertices of T, respectively. (For the sake of simplicity, we include the two endpoints of T in both ${\mathscr {R}}$ and ${\mathscr {C}}$). In the following we state a well-known result from Claim 3.3 and 3.4 of [17], which states that guarding convex vertices of an orthogonal terrain using guards placed at reflex vertices is enough to guard the whole terrain. This property will be useful in our algorithm.

Proposition 2

[17] (T, k) is a yes-instance of Discrete Orthogonal Terrain Guarding if and only if there is $S\subseteq {\mathscr {R}}$ of size at most k such that S sees each vertex of ${\mathscr {C}}$.

Observation 10

For an orthogonal terrain T and vertices $u=(x_u,y_u)\in {\mathscr {R}}$ and $v=(x_v,y_v)\in {\mathscr {C}}$, if u sees v, then $y_v \le y_u$.

Next we will define the notion of valleys. Roughly speaking, a “valley” is a maximal region containing at most one minimum and at most two maxima. We will formally define the notion of valleys in an orthogonal terrain; our definitions will be formulated in a way to ensure uniqueness of the set of valleys in the given terrain (see Fig. 7).

Fig. 7

An intuitive illustration of the set of valleys ${\mathcal {W}} = \{W_1,W_2,W_3,W_4\}$ and different vertices in an orthogonal terrain. (The sets are presented modulo the elements $-\infty$ and $+\infty$.)

Definition 4

For an integer $i \ge 1$, the $i^{th}$valley, denoted by ${W}_i$ (with its vertex set denoted by $V(W_i)$), of the terrain T is an (ordered) set of consecutive vertices of T that contains the smallest vertex u that is not contained in any valley $W_j$, where $j<i$, and the following vertices.⁴ Let $a < n$ be the smallest integer (if it exists) such that $(v_a,v_{a+1}) \in \mathsf{Max}(T)$ and $v_a, v_{a+1} \notin \cup _{j < i} V({W}_{j})$. If a does not exist, then ${W}_i$ contains all the vertices v where $u \preceq v \preceq v_n$. Otherwise, ${W}_i$ contains all the vertices v where $u \preceq v \preceq v_{a+1}$.

We let ${\mathcal {W}} = \{W_1, W_2, \ldots , W_t\}$ be the set of valleys in T. Notice that $t \le |\mathsf{Min}(T)|+2$. For a valley $W_i = (v_f, v_{f+1}, \ldots ,$ $v_\ell ) \in {\mathcal {W}}$, the vertices $\mathsf{fst}(i) = v_f$ and $\mathsf{lst}(i) = v_\ell$ denote the first and last vertices of $W_i$, respectively. For the sake of notational convenience, we will now define left/right slope convex vertices. We say that $W_i$ contains a minimum/maximum $(v_a,v_{a+1})$, if $v_a,v_{a+1} \in V(W_i)$. Note that by definition, $W_i$ can contain at most one minimum and at most two maxima. If $W_i$ has one minimum, say $(v_a,v_{a+1})$, then the set of left slope vertices $L_i$, is the set $\{v_f, v_{f+1}, \ldots ,v_a\}$ and the set of right slope vertices $R_i$, is the set $\{v_{a+1}, v_{a+2}, \ldots ,v_\ell \}$. Otherwise, the vertices $(v_f, v_{f+1}, \ldots ,v_\ell )$ have either non-increasing y-coordinates or non-decreasing y-coordinates. If $(v_f, v_{f+1}, \ldots ,v_\ell )$ have non-increasing y-coordinates, then we have $L_i = V(W_i)$ and $R_i=\emptyset$. Otherwise, $(v_f, v_{f+1}, \ldots ,v_\ell )$ have non-decreasing y-coordinates, and we have $R_i = V(W_i)$ and $L_i=\emptyset$. We let ${\mathscr {R}}_i = V(W_i) \cap {\mathscr {R}}$, ${\mathscr {C}}^\mathsf{lft}_i = (L_i \cap {\mathscr {C}}) \cup \{-\infty \}$, ${\mathscr {C}}^\mathsf{rht}_i = (R_i \cap {\mathscr {C}}) \cup \{+\infty \}$ (see Figs. 7, 8).⁵ We let $p^\mathsf{lft}_i$ be the largest vertex in ${\mathscr {C}}^\mathsf{lft}_i$. Similarly, we let $\widehat{p}^\mathsf{rht}_i$ be the smallest vertex in ${\mathscr {C}}^\mathsf{rht}_i$. We will now define the set of heights H of guards in the terrain, which will be used in defining the states of our dynamic programming routine: $H = \{y \mid v = (x,y) \in {\mathscr {R}}\} \cup \{+\infty \}$. For $y \in H {\setminus } \{+\infty \}$, by $\mathsf{prv}(y)$ we denote the smallest element $y' \in H$ such that $y' > y$. (For the largest element, say $y^* \in H {\setminus } \{+\infty \}$, we have $\mathsf{prv}(y^*) = +\infty$.) Finally for $i\in [t]$, we let ${\mathcal {S}}_i = {\mathscr {C}}^\mathsf{lft}_i \times {\mathscr {C}}^\mathsf{rht}_i$.

We state some useful observations that will be useful in our algorithm. We will move to the description of the states of our dynamic programming table after the stating few simple but useful observations below.

Observation 11

Consider $i\in [t]$. For a vertex $v_{j}=(x_j,y_j)\in {\mathscr {C}}^\mathsf{lft}_i$, if $v_\ell =(x_\ell ,y_\ell )\in {\mathscr {R}}$ sees $v_j$ and $\ell <j$, then $\ell = j-1$. Similarly, a vertex $v_j=(x_j,y_j)\in {\mathscr {C}}^\mathsf{rht}_i$, if $v_\ell =(x_\ell ,y_\ell )\in {\mathscr {R}}$ sees $v_j$ and $j<\ell$, then $\ell = j+1$.

Observation 12

Consider $i\in [t]$, and vertices $v_{j_1}=(x_{j_1},y_{j_1}), v_{j_2}=(x_{j_2},y_{j_2})\in {\mathscr {C}}^\mathsf{lft}_i$, where $j_1 < j_2$. If $v_\ell =(x_\ell ,y_\ell )\in {\mathscr {R}}$ sees $v_{j_2}$, where $j_2 < \ell$, and $y_{j_1} \le y_\ell$, then $v_\ell$ sees $v_{j_1}$.

We define the set of heights of guards in a valley, which will be useful in stating the states of our dynamic programming routine. For $i\in [t]$, we let $\mathsf{Hgt}(i) = \{y_a \mid v_a = (x_a,y_a) \in {\mathscr {R}}_i\} \cup \{+\infty \}$. Moreover, for $y_a \in \mathsf{Hgt}(i) {\setminus } \{+\infty \}$, by $\mathsf{prv}_i(y_a)$ we denote the smallest element $y_{a'} \in \mathsf{Hgt}(i)$ such that $y_{a'} > y_a$. (For the largest element, say $y^*_a \in \mathsf{Hgt}(i) {\setminus } \{+\infty \}$, we have $\mathsf{prv}_i(y_a) = +\infty$.) Finally for $i\in [t]$, we let ${\mathcal {S}}_i = {\mathscr {C}}^\mathsf{lft}_i \times {\mathscr {C}}^\mathsf{rht}_i \times \mathsf{Hgt}(i)$.

We let ${\mathscr {R}}^\mathsf{lft}_i = ({\mathscr {R}}^\mathsf{lft} \cap V(W_i)) \cup \{+\infty \}$, ${\mathscr {R}}^\mathsf{rht}_i = ({\mathscr {R}}^\mathsf{rht} \cap V(W_i)) \cup \{-\infty \}$, ${\mathscr {C}}^\mathsf{lft}_i = ({\mathscr {C}}^\mathsf{lft} \cap V(W_i))\cup \{-\infty \}$ and ${\mathscr {C}}^\mathsf{rht}_i = ({\mathscr {C}}^\mathsf{rht} \cap V(W_i)) \cup \{+\infty \}$. Furthermore, we let ${\mathcal {S}}_i = {\mathscr {C}}^\mathsf{lft}_i \times {\mathscr {C}}^\mathsf{rht}_i \times {\mathscr {R}}^\mathsf{rht}_i \times {\mathscr {R}}^\mathsf{lft}_i$.

We are now ready to define the states of our dynamic programming algorithm. For each valley we will have the following in our dynamic programming states. Firstly, we have a pair of vertices from each valley, one from the left-side and other from the right-side of the valley. These two vertices tell us “what” vertices must be guarded (see Fig. 8 for an illustration). Intuitively speaking, we want to guard all the left (resp. right) convex vertices in the valley that are on or above the left-side (resp. right-side) vertex for this valley in the state of our dynamic programming table. Additionally, we have a number denoting the height, on or above which we are allowed to place the guards. Apart from these, we will have a number $k' \le k$ denoting the number of guards that we are allowed to use in our “partial” solution.

Fig. 8

An intuition of states of our dynamic programming algorithm

States of the Dynamic Programming Table and Their Interpretation Consider $\tau = (\tau _1, \tau _2, \ldots ,$ $\tau _t) \in {\mathcal {S}}_1\times {\mathcal {S}}_2 \times \cdots \times {\mathcal {S}}_t$, where for $i\in [t]$, $\tau _i = (p_i,{\widehat{p}}_i) \in {\mathcal {S}}_i$, $h\in H$, and an integer $k' \in \{0,1,2,\ldots , k\}$. For each such triple we have an entry in our dynamic programming table denoted by $\Pi (\tau ,h,k')$. For interpreting $\Pi (\tau ,h,k')$, we will define $\Gamma (\tau ,h,k')$; the goal of the algorithm will be to compute $\Pi (\tau ,h,k')$, so as to mimic $\Gamma (\tau ,h,k')$, for every triple.

Definition 5

For $\tau = (\tau _1, \tau _2, \ldots ,$ $\tau _t) \in {\mathcal {S}}_1\times {\mathcal {S}}_2 \times \cdots \times {\mathcal {S}}_t$, where for $i\in [t]$, $\tau _i = (p_i,{\widehat{p}}_i) \in {\mathcal {S}}_i$, $h\in H$, and an integer $k' \in \{0,1,2,\ldots , k\}$, we have $\Gamma (\tau ,h,k')=1$ if and only if there is a set $S\subseteq {\mathscr {R}}$ of size at most $k'$ such that the following conditions are satisfied (see Fig. 8):

• 1. All the guards placed are at height at least h. That is, for each $v = (x,y) \in S$, we have $y \ge h$.

• 2. Each vertex in ${\mathscr {C}}^\mathsf{lft}_i$ that is $p_i$ or above it, is seen by a guard in S. Similarly, each vertex in ${\mathscr {C}}^\mathsf{rht}_i$ that is $\widehat{p}_i$ or above it, is seen by a guard in S. So, for each $i\in [t]$ and $u \in {\mathscr {C}}^\mathsf{lft}_i \cup {\mathscr {C}}^\mathsf{rht}_i$, such that either $\mathsf{fst}(i) \preceq u \preceq p_i$ or ${\widehat{p}}_i \preceq u \preceq \mathsf{lst}(i)$, there is $w \in S$ that sees u.

In the above, the set S is called a solution for $(\tau ,h,k')$.

Let $h^* = \min \{y \in H\}$, and $\tau ^*_i = (p^\mathsf{lft}_i, \widehat{p}^\mathsf{rht}_i)$, for each $i\in [t]$. (In the above, for $i\in [t]$, as $-\infty \in {\mathscr {C}}^\mathsf{lft}_i$ and $+\infty \in {\mathscr {C}}^\mathsf{rht}_i$, $p^\mathsf{lft}_i$ and $\widehat{p}^\mathsf{rht}_i$ can never be undefined.) From Proposition 2 we can obtain that (T, k) is a yes-instance of Discrete Orthogonal Terrain Guarding if and only if $\Gamma (\tau ^*_1, \tau ^*_2, \ldots , \tau ^*_t, h^*, k) = 1$.

Order of Computation of Entries We describe the order in which we compute the entries of our dynamic programming table. We will use a modified form of “lexicographic” ordering for the table entries as follows. To this end we first describe how we order the vertices in the “left” and “right” sides of our valleys. For $i \in [t]$, the vertices in ${\mathscr {C}}^\mathsf{lft}_i$ are ordered as per the ordering given by T, whereas, the vertices in ${\mathscr {C}}^\mathsf{rht}_i$ are reverse ordered compared to the ordering given by T. (We need to do the above because when are going down the valley from right side, the vertices are decreasing.) We order the elements of H in decreasing order (with $+\infty$ being the first element in this ordering). Finally, the overall ordering is obtained by using (lexicographic) ordering of H, the ordering of vertices in ${\mathscr {C}}^\mathsf{lft}_i$, and the ordering of vertices in ${\mathscr {C}}^\mathsf{rht}_i$, with increasing values of i, and $k'$ (increasing).

Next we will describe how we (recursively) compute the entries of the table. Consider $\tau = (\tau _1, \tau _2, \ldots , \tau _t) \in {\mathcal {S}}_1\times {\mathcal {S}}_2 \times \cdots \times {\mathcal {S}}_t$, where for $i\in [t]$, $\tau _i = (p_i,{\widehat{p}}_i)$, $h\in H$, and an integer $k' \in \{0,1,2,\ldots , k\}$. We compute $\Pi (\tau ,h,k')$ as follows.

Base Cases The base cases occur in the following scenarios, applied in the given order.

• 1. If for each $i \in [t]$, we have $p_i = -\infty$ and $\widehat{p}_i = +\infty$, then $\Pi (\tau ,h,k') = 1$.

• 2. If $k=0$ and for some $i \in [t]$, $p_i \ne -\infty$ or $\widehat{p}_i \ne +\infty$, then $\Pi (\tau ,h,k') = 0$.

• 3. If $h = +\infty$ and for some $j\in [t]$, $p_j \ne -\infty$ or $\widehat{p}_j \ne +\infty$, then $\Pi (\tau ,h,k') = 0$.

The correctness of the base cases directly follows from their description. Next we describe the recursive formula for computing the other entries of our dynamic programming table.

Recursive Formula Intuitively, we will compute an entry by taking “or” of the solutions for already computed entries, where the entries we query are based on where and at what vertices we place the lowest height guards in the partial solution.

Let $A_h= \{v=(x,y) \in {\mathscr {R}} \mid \text{ and } y = h\}$. As Item 1 of Base Case is not applicable, we need to place at least one guard, thus we can obtain that $H \ne \emptyset$. Notice that $|A_h| \le 2t$, as for each valley, we can have at most two vertices from ${\mathscr {R}}$ that are at height h. For every $A \subseteq A_h$, we will compute $\rho _{A}$, which (intuitively speaking) corresponds to the solution S for $(\tau ,h,k')$, where $S \cap A_h = A$, i.e., A is the set of (vertex) guards at height h in the solution. (We will have $\rho _{A} =1$ if and only if there is a solution S for $(\tau ,h,k')$ such that $S \cap A_h = A$.)

We remark that $h \ne +\infty$, as the base cases are not applicable. Consider $A\subseteq A_h$. If some $a\in A$ sees $p_i$, then we let $p_i[A]$ be the largest vertex in ${\mathscr {C}}^\mathsf{lft}_i$ that is not seen by any vertex in A. (If $p_i[A]$ does not exists, it is set to $-\infty$.) Otherwise, no $a\in A$ sees $p_i$, and we set $p_i[A] = p_i$. Similarly, if some $a\in A$ sees $\widehat{p}_i$, we let $\widehat{p}_i[A]$ be the smallest vertex in ${\mathscr {C}}^\mathsf{rht}_i$ that is not seen by any $a\in A$. (If $\widehat{p}_i[A]$ does not exists, it is set to $+\infty$.) Otherwise, no $a\in A$ sees $\widehat{p}_i$, and we set $\widehat{p}_i[A] = \widehat{p}_i$. Let $\tau _i[A] = ({p}_i[A],\widehat{p}_i[A])$. Finally, we let $\tau [A] = (\tau _1[A], \tau _2[A], \ldots , \tau _t[A])$. Notice that $(\tau [A], \mathsf{prv}(h), k'- |A|)$ is smaller in order compared to $(\tau ,h,k)$, and thus the entry corresponding to it in our dynamic programming table is already computed. We let $\rho _A = \Pi (\tau [A], \mathsf{prv}(h), k'- |A|)$. Finally, we set $\Pi (\tau ,h,k') = \vee _{A \subseteq A_h}\rho _{A}$.

Lemma 4

The recursive formula for computation of the entries is correct.

Proof

To establish the correctness it is enough to show that $\Gamma (\tau ,h,k') = 1$ if and only if there is $A\subseteq A_h$, such that $\rho _A = \Pi (\tau [A], \mathsf{prv}(h), k'- |A|) = 1$.

For the forward direction suppose that $\Gamma (\tau ,h,k') = 1$, and $S\subseteq {\mathscr {R}}$ be a solution for $(\tau ,h,k')$. We let $A^* = S\cap A_h$ and $S^* = S{\setminus } A^*$. We will show that $\rho _{A^*} = \Pi (\tau [A^*], \mathsf{prv}(h), k'- |A^*|) = 1$. We will show that $\Pi (\tau [A^*], \mathsf{prv}(h), k'- |A^*|) = 1$, by proving that $S^*$ is a solution for $(\tau [A^*], \mathsf{prv}(h), k'- |A^*|)$. As S is a solution for $(\tau ,h,k')$, for each $v= (x,y)\in S$, we have $y \ge h$. The above together with the construction of $S^*$ (and $A_h$) implies that for each $v= (x,y)\in S^*$, we have $y \ge \mathsf{prv}(h)$, and $|S^*| \le k'-|A^*|$. Now it remains to prove Item 2 of Definition 5, to show that $S^*$ is a solution for $(\tau [A^*], \mathsf{prv}(h), k'- |A^*|)$. Consider $i\in [t]$. We will show that for each $u \in {\mathscr {C}}_i$, such that either $\mathsf{fst}(i) \preceq u \preceq p_i[A^*]$ or $\widehat{p}_i[A^*] \preceq u \preceq \mathsf{lst}(i)$, there is some $s\in S^*$ that sees u. We will only prove the above statement for the case when $\mathsf{fst}(i) \preceq u \preceq p_i[A^*]$. (We can obtain the proof for the case when $\widehat{p}_i[A^*] \preceq u \preceq \mathsf{lst}(i)$, by following similar arguments.) Let $u =(x_u,y_u) \in {\mathscr {C}}^\mathsf{lft}_i$ be the largest vertex such that $\mathsf{fst}(i) \preceq u \preceq p_i[A^*]$ and u is not seen by any vertex in $S^*$. (If such a vertex u does not exist, then the claim trivially follows.) Since S is a solution for $(\tau ,h,k')$ and (by construction) $p_i[A^*] \le p_i$, there exists $s = (x,h) \in S {\setminus } S^* = A^*$, such that s sees u. Furthermore, there is $s'=(x',y') \in S^*$, where $h<y'$, such that $s'$ sees $p_i[A^*]$. From the above we can obtain that all of $u, p_i[A^*],s,s'$ are distinct and $u \prec p_i[A^*]$. From Observation 10 we have $y_u \le h$. This together with the fact that $h<y'$ implies that $y_u < y'$. If $p_i[A^*] \prec s'$, then using Observation 12 we can conclude that $s'$ sees u. This contradicts the choice of u that no vertex in $S^*$ sees it. Now consider the case when $s' \prec p_i[A^*]$. In this case, using Observation 11 we can obtain that $u \prec s' \prec p_i[A^*]$. Thus, we have $y_u \ge y'$. As $y'> h$, using Observation 10 we can obtain a contradiction to our assumption that $s=(x,h)$ sees u. This concludes the proof of the forward direction.

Now we consider the reverse direction. Consider $A^*\subseteq A_h$, such that $\rho _{A^*} = \Pi (\tau [A^*], \mathsf{prv}(h),$ $k'- |A^*|) = 1$, and let $S^*$ be a solution for $(\tau [A^*], \mathsf{prv}(h),$ $k'- |A^*|)$. Let $S = S^* \cup A^*$. Clearly, $|S| \le k'$, and for each $v = (x,y) \in S$, we have $y \ge h$. Also, for $i\in [t]$, by the construction of $p_i[A^*]$ and $\widehat{p}_i[A^*]$, and the fact that $S^*$ is a solution for $(\tau [A^*], \mathsf{prv}(h),k'- |A^*|)$, we can conclude that for each $u \in {\mathscr {C}}^\mathsf{lft}_i \cup {\mathscr {C}}^\mathsf{rht}_i$, such that either $\mathsf{fst}(i) \preceq u \preceq p_i$ or ${\widehat{p}}_i \preceq u \preceq \mathsf{lst}(i)$, there is $s \in S$ that sees u. From the above discussions we can obtain that S is a solution for $(\tau ,h,k')$, and thus we have $\Gamma (\tau ,h,k') = 1$. This concludes the proof. $\square$

Note that t, the number of valleys, is bounded $|\mathsf{Min}(T)|+2$. The number of entries in our dynamic programming table is bounded by $n^{2t+{\mathcal {O}}(1)}$. The entries in our base cases can be computed in $\mathcal {O}(1)$ time. The recursive formula per entry can be computed in time bounded by $2^{2t}\cdot n^{{\mathcal {O}}(1)}$, as $|A_h| \le 2t$, for each $h \in H$. Thus we obtain the proof of Theorem 2.