On the Hardness of Some Geometric Optimization Problems with Rectangles

Abstract

We study the Set Cover, Hitting Set, Piercing Set, Independent Set, Dominating Set problems, and discrete versions (Discrete Independent Set and Discrete Dominating Set) for geometric instances in the plane. We focus on certain restricted classes of geometric objects, including axis-parallel lines, strips, and rectangles. For rectangles, we consider the cases in which the rectangles are (i) anchored on a horizontal line, (ii) anchored on two lines (either two parallel lines or one vertical and one horizontal line), and (iii) stabbed by a horizontal line. Some versions of these problems have been studied previously; we focus here on the open cases, for which no complexity results were known.

1 Introduction

We study several special cases of various optimization problems in the plane, including the Set Cover (SC), Hitting Set (HS), Piercing Set (PS), Independent Set (IS), and Dominating Set (DS) problems. In addition, we consider versions of the IS and DS problems, the Discrete Independent Set (DIS) and Discrete Dominating Set (DDS) problems. The inputs of these two problems are a set of objects O and a set of points P. In the DIS problem the objective is to select maximum cardinality subset $O'\subseteq O$ of objects such that any two objects in $O'$ do not share a point in P. On the other hand, in the DDS problem the objective is to select a minimum collection $O'\subseteq O$ of objects such that the intersection of any object in $O\setminus O'$ and an object in $O'$ contains a point in P.

In this paper we study various optimization problems on various types of geometric objects as follows (see Fig. 1 for some types of objects):

➟:

Line: Axis parallel lines.

➟:

Strip: Axis-parallel strips.

➟:

R-AHL: Rectangles anchored on a horizontal line (Fig. 1(a)).

➟:

R-ATL: Rectangles anchored on two lines (Fig. 1(b)).

➟:

R-ATOL: Rectangles anchored on two orthogonal lines (Fig. 1(c)).

➟:

R-SHL: Rectangles stabbing a horizontal line.

Fig. 1.

(a) Rectangles anchored on a horizontal line. (b) Rectangles anchored on two lines. (c) Rectangles anchored on two orthogonal lines.

1.1 Previous Work

The optimization problems considered in this paper are $\mathsf {NP}$-hard for simple geometric objects like unit squares [9], unit disks [9], rectangles [9], etc. The SC problem admits a $\mathsf {PTAS}$ for weighted unit squares [8]. The SC and HS problems are $\mathsf {APX}$-hard even for axis-parallel strips [5]. For rectangles anchored on a horizontal line both the SC and HS problems can be solved in polynomial time [5, 11]. When the rectangles are anchored on two lines both these problems are $\mathsf {NP}$-hard [18]. Chepoi and Felsner [6] considered the IS and PS problems with rectangles where the rectangles are intersecting an axis-monotone curve. Correa et al. [7] studied the same problem, where the objects intersect a diagonal line. In [17], their results were extended. They also considered the SC and HS problems with other geometric objects as well.

In [19], the author studied the DS problem using axis-parallel rectangles and unit squares where the objects are intersecting a straight line which makes an angle with the x-axis. Recently, Bandyapadhyay et al. [3] gave a $\mathsf {PTAS}$ for the DS problem with axis-parallel rectangles touching a line with slope -1 from exactly one side of the line. Recently, Madireddy et al. [16] studied the DDS and DIS problem with arbitrary radii disks and arbitrary length squares in the plane and provide $\mathsf {PTAS}$es. They also showed that both DDS and DIS problems are $\mathsf {NP}$-hard for unit disks intersecting a horizontal line and for axis-parallel unit squares intersecting a straight line with slope $-1$. In [20], the author studied the SC, HS, PS, and IS problems with right angled triangles such that the triangles intersect a straight line (either a horizontal line or a line with slope of $-1$).

1.2 Our Contributions

We list our contributions in Table 1.

Table 1. Our contributions are shown in colored text (P-> polynomial time, H-> $\mathsf {NP}$-hard). The results in non-colored text for which no references are given are either trivial to show or can be derived from the other problems easily.

1.3 Prerequisites

In a ( ) problem we are given a 3-CNF formula $\phi$ with n variables $x_1, x_2,\ldots , x_n$ and m clauses $C_1, C_2,\ldots , C_m$ such that each clause contains exactly 3 literals. For each variable or clause take a vertex in the plane. A literal is present in a clause if and only if there is an edge between the two vertices corresponding to the variable and the clause. Moreover, the formula should be such that the resulting graph must be planar. The goal is now to decide whether there is a truth assignment to the variables such that $\phi$ is satisfiable. Lichtenstein [15] proved that this problem is $\mathsf {NP}$-complete. Later on Knuth and Raghunathan [13] considered a restricted version of the problem, the ( ) problem can be defined as follows. For each variable or clause we take a horizontal line . The variable segments are placed on a horizontal line and clause segments are connected to these variable segments either from above or below by vertical line segments called such that none of these line segments and connections intersect. The goal is to decide whether there is a truth assignment to the variables such that $\phi$ is satisfiable. Figure 2 shows an instance of the R-P-3-SAT problem. Knuth and Raghunathan [13] showed that every problem instance has an equivalent problem instance and hence the later problem is also $\mathsf {NP}$-complete. Note that we can order the variable segments in increasing x direction. Let $C_t = (x_i\vee x_j\vee x_k)$ be a clause that connects the variables from above, where $x_i$, $x_j$, $x_k$ are ordered in the above ordering. Then we say that, $x_i$ is a , $x_j$ is a , $x_k$ is a variable.

2 Discrete Dominating Set

2.1 Axis-Parallel Lines

We prove that the DDS-Line problem is $\mathsf {NP}$-hard. The reduction is from the minimum dominating set problem on bipartite graphs that is $\mathsf {NP}$-complete [4]. Let G(A, B, E) be a bipartite graph where the vertices of A are on a vertical line and the vertices or B are on another vertical line to the right of A. Let $1,2,\ldots ,\tau$ be the number of the vertices of A from top to bottom. Similarly, let $1,2,\ldots ,\kappa$ be the number of the vertices of B from top to bottom. Now for each vertex $i \in A$, take a horizontal line $h_i$ as $y=i$ and for each vertex $j\in B$ take a vertical line $v_j$ as $x=j$. Let $e_{ij}=(i,j)$ such that $i\in A \text {~and~} j\in B$ be an edge in E. Take a point $p_{ij}$ with coordinate (i, j) corresponding to $e_{ij}$ at the intersection of $h_i$ and $v_j$. See Fig. 3 for this construction. This construction takes polynomial time. It is observed that finding a minimum set of vertices in G that dominates all the vertices in G is equivalent to finding a minimum set of axis-parallel lines that dominates all the lines. Hence we conclude:

Fig. 2.

An instance of problem. Solid (resp. dotted) clause vertical segments represent that the variable is positively (resp. negatively) present in the corresponding clauses. For clause $C_4$, $x_1$ is a left, $x_4$ is a middle, and $x_5$ is a right variable.

Theorem 1

DDS-Line is $\mathsf {NP}$-hard.

Fig. 3.

(a) An instance of a bipartite graph. (b) An instance of the DDS-Line problem constructed from the instance in (a).

Corollary 1

The $\mathsf {NP}$-hardness of the DDS-Line problem directly implies the $\mathsf {NP}$-hardness of the DDS-Strip problem by replacing each horizontal (resp vertical) line by a thin horizontal (resp vertical) strip. The $\mathsf {NP}$-hardness of the DDS-Strip problem shows the $\mathsf {NP}$-hardness of the DDS-R-ATOL problem. We just take a vertical and a horizontal line both at $-\infty$. Clearly these lines restrict the horizontal and vertical strips at $-\infty$.

2.2 Rectangles Anchored on Two Lines

We prove that the DDS-R-ATL problem is $\mathsf {NP}$-hard by a reduction from the R-P-3-SAT problem (see prerequisites).

Reduction: To represent a variable gadget of the DDS-R-ATL problem, we assume the graph G in Fig. 4. The following result on G can be proved easily.

Lemma 1

There are exactly two optimal dominating sets, $D_0 \,{=}\, \{v_{4},v_{8},\ldots ,v_{8\alpha }\}$ and $D_1 = \{v_{2},v_{6},\ldots ,v_{8\alpha -2}\}$, of vertices each with cost exactly $2\alpha$ for graph G.

We choose $\alpha$ to be the maximum number of clause vertical connections connecting from clause segments to a single variable segment either from above or from below. We encode the graph in Fig. 4 as a variable gadget of the DDS-R-ATL problem. For each vertex, we take a rectangle and for each edge, we take a point that is contained in exactly the rectangle corresponding to the two vertices that form the edge. The gadget for the variable $x_i$ is shown in Fig. 5. We take $8\alpha$ rectangles $R_i$ and $10\alpha$ points $P_i$ in two sides of a horizontal line L. The $4\alpha$ rectangles $\{s_1^i, s_2^i,\ldots ,s_{4\alpha }^i\}$ and $5\alpha$ points $\{p_1^i, p_2^i,\ldots ,p_{5\alpha }^i\}$ are one side of L and the $4\alpha$ rectangles $\{s_{4\alpha +1}^i, s_{4\alpha +2}^i,\ldots ,s_{8\alpha }^i\}$ and $5\alpha$ points $\{p_{5\alpha +1}^i, p_{5\alpha +2}^i,\ldots ,p_{10\alpha }^i\}$ are another side L. Therefore, by Lemma 1 we conclude that for each variable gadget there are exactly two optimal dominating set of rectangles $S_i^0 = \{s_{4}^i,s_{8}^i,\ldots ,s_{8\alpha }^i\}$ and $S_i^1 = \{s_{2}^i,s_{6}^i,\ldots ,s_{8\alpha -2}^i\}$; each with size exactly $2\alpha$. This represents the truth value of the variable $x_i$.

Fig. 4.

Structure of the graph G.

The construction of the clause gadgets in the above and below are independent, and hence we describe the clause gadgets only for the above. For a clause $C_t$ that contains three variables $x_i$, $x_j$ and $x_k$ in this order from left to right, we take a rectangle $r^t$ and three points $p^{t_i}, p^{t_j}, p^{t_k}$. The bottom boundary of $r^t$, say $b^t$, are on the horizontal segment of $C_t$. In Fig. 6, we give a schematic diagram of the clause rectangles and positions of the points corresponding to the clauses. We now describe how $r^t, p^{t_i}, p^{t_j}, p^{t_k}$ interact with the variable gadgets.

Fig. 5.

Structure of a variable gadget.

Fig. 6.

Schematic diagram of the clause rectangles and position of the points (circles) and their interaction with the variable gadget.

For each variable $x_i$, $1\le i \le n$, sort the vertical connections from left to right that connect to $x_i$ from clauses connecting from above. Let the clause $C_t$ connects to $x_i$ via l-th connection, then we say that $C_t$ is the l-th clause for $x_i$.

Let $C_t$ be a clause containing the three variables $x_i$, $x_j$ and $x_k$ in this order from left to right. Here $x_i$ is a left variable in the clause $C_t$ and let $C_t$ be the $l_1$-th clause for $x_i$. If $x_i$ occurs as a positive literal in $C_t$, then we place the point $p_{t_i}$ on $b^t$ and inside the rectangle $s_{4l_1+4}^i$ only. Otherwise, we place the point $p_{t_i}$ on $b^t$ and inside the rectangle $s_{4l_1+2}^i$ only. The interaction is similar for $x_j$ (middle variable) and $x_k$ (right variable) by replacing $l_1$ with $l_2$ and $l_3$ respectively. See Fig. 7 for the above construction. Clearly, the above construction can be done in polynomial time. We now prove the correctness of the above construction.

Fig. 7.

Structure of a clause gadget and its interaction with variable gadgets.

Lemma 2

The formula $\phi$ is satisfiable iff there exists a solution to ${\mathscr {D}}$, an instance of the DDS-R-ATL problem constructed from $\phi$, with cost at most $2\alpha n$.

Proof

Assume that $\phi$ is satisfiable and let $A: \{x_1,x_2, \ldots , x_n\} \rightarrow \{true,false\}$ be a satisfying assignment. For the i-th variable gadget, take the solution $S_i^0$, if $A(x_i) =true$. Otherwise take $S_i^1$. Clearly, we choose a total of $2\alpha n$ rectangles and these rectangles dominate all the variable and clause rectangles.

On the other hand, suppose that there is a solution to ${\mathscr {D}}$ with cost at most $2\alpha n$. To dominate all the half-strips in a variable gadget requires at least $2\alpha$ rectangles (see Claim 1). Note that all the variable gadgets are disjoint. Therefore, from each variable gadget we must choose exactly $2\alpha$ rectangles (either set $S_i^0$ or set $S_i^1$). Set a variable to true if $S_i^0$ is chosen in its variable gadget, otherwise set it to false. Note that there are three points in a clause rectangle. Since the clause rectangle is dominated, at least one of these three points is covered by the solution. Such a point is either in solution $S_i^0$ or in solution $S_i^1$ of the corresponding variable gadget based on whether the variable is positively or negatively present in the clause. Hence, the assignment is a satisfying assignment.    $\square$

Theorem 2

The DDS-R-ATL problem is $\mathsf {NP}$-hard.

2.3 Rectangles Stabbed by a Horizontal Line

We prove that the DDS-R-SHL problem is $\mathsf {NP}$-hard. The reduction is similar to the reduction given in Sect. 2.2. Here also we encode the graph G in Fig. 4 as a variable gadget (see Fig. 8(a)). Note that in Fig. 8(a), all the rectangles are anchored on L except $s_{4\alpha }^i$ and $s_{8\alpha }^i$ that is stabbed in the middle by L. Clearly, using Lemma 1, we say that for each variable gadget there are exactly two optimal dominating sets of rectangles each with size $\alpha$: $S_i^0 = \{s_{4}^i,s_{8}^i,\ldots ,s_{8\alpha }^i\}$ and $S_i^1 = \{s_{2}^i,s_{6}^i,\ldots ,s_{8\alpha -2}^i\}$. These two sets represent the truth value of $x_i$.

The clause gadgets are exactly the same as the clause gadgets in Sect. 2.2. However, here the interaction between the clause gadgets and the variable gadgets is different. We first reverse the connection of the clauses in the R-P-3-SAT problem instance i.e., the clauses those connect the variables from above (resp below) are now connect the variables from below (resp above). Now observe that the description of the variable clause connection for the clauses that connects to the variable from above in Sect. 2.2 are true here for the variable clause connection for the clauses that connects to the variable from below. In Fig. 8, we give a schematic diagram of the clause rectangle and position of the points corresponding to the clauses. A similar proof of Theorem 2 concludes:

Theorem 3

The DDS-R-SHL problem is $\mathsf {NP}$-hard.

Fig. 8.

(a) A variable gadget. (b) Schematic diagram of the variable and clause gadgets and their interaction. Blue rectangles are schematically represent the variable gadgets. (Color figure online)

3 Discrete Independent Set

3.1 Axis-Parallel Lines

We show that the DIS-LINE problem can be solved in polynomial time. We consider the reduction in the Sect. 2.1 in the reverse reduction, which ensures that finding a solution to the DIS-LINE problem is equivalent to finding a solution to the maximum independent set problem in a bipartite graph. Since the later problem can be solved in polynomial time, the DIS-LINE problem can also be solved in polynomial time.

Theorem 4

The DIS-Line problem can be solved in polynomial time.

3.2 Rectangles Anchored on Two Lines

We prove that the DIS-R-ATL problem is $\mathsf {NP}$-hard. We give a reduction from the R-P-3-SAT problem (see prerequisites).

Reduction: Note that, we choose $\alpha$ to be the maximum number of clause vertical connections connecting from clause segments to a single variable segment either from above or from below. The gadget for the variable $x_i$ is shown in Fig. 9(a). We take $16\alpha$ rectangles and $16\alpha$ points in two sides of a horizontal line L. The $8\alpha$ rectangles $\{s_1^i, s_2^i,\ldots ,s_{8\alpha }^i\}$ and $8\alpha$ points $\{p_1^i, p_2^i,\ldots ,p_{8\alpha }^i\}$ are one side of L and the $8\alpha$ rectangles $\{s_{8\alpha +1}^i, s_{8\alpha +2}^i,\ldots ,s_{16\alpha }^i\}$ and $8\alpha$ points $\{p_{8\alpha +1}^i, p_{8\alpha +2}^i,\ldots ,p_{16\alpha }^i\}$ are another side of L. Each pair of consecutive rectangles have a point in common. Since these rectangles forms a cycle graph, where rectangles corresponding to vertices and two rectangles share a point if and only if there is an edge between the corresponding vertices of these two rectangles.

Observation 1

For each variable gadget there are exactly two optimal independent sets of rectangles $H_i^0 = \{s_{2}^i,s_{4}^i,\ldots ,s_{16\alpha }^i\}$ and $H_i^1 = \{s_{1}^i,s_{3}^i,\ldots ,s_{16\alpha -1}^i\}$ each with size exactly $8\alpha$.

The construction of the clause gadgets in above and below are independent, and hence we describe the clause gadgets only for above. Let $C_t$ be a clause that contains variables $x_i$, $x_j$ and $x_k$ in this order from left to right. For $C_t$, we take 5 rectangles $\{s_1^t,s_2^t,s_3^t,s_4^t,s_5^t\}$ and 6 points; 1 point $p^{t_i}$ corresponding to $x_i$, 4 points $p^{t_j}_1,p^{t_j}_2,p^{t_j}_3,p^{t_j}_4$ corresponding to $x_j$, and 1 point $p^{t_k}$ corresponding to $x_k$. The rectangle $s_1^t$ covers the points $\{p^{t_i},p^{t_j}_1,p^{t_j}_4\}$, $s_2^t$ covers $\{p^{t_i},p^{t_j}_1,p^{t_j}_2\}$, $s_3^t$ covers $\{p^{t_j}_2,p^{t_j}_3\}$, $s_4^t$ covers $\{p^{t_j}_1,p^{t_j}_2,p^{t_j}_4, p^{t_k}\}$, and $s_5^t$ covers $\{p^{t_j}_1,p^{t_j}_4,p^{t_k}\}$. See Fig. 10 for this construction. We now describe the placement of the points and rectangles with respect to the variable gadget. We take a rectangle $r^t$. The bottom boundary of $r^t$, say $b^t$, are on the horizontal segment of $C_t$ and it can extends to the infinity (actually we can take horizontal line in a far enough distance such that the top boundaries of all such rectangles touch it) in the upward direction. We take a horizontal thin rectangular along the top edge of $r^t$. We place points corresponding to the clause $C_t$ inside this region. The rectangles corresponding to $C_t$ are exclusively in $r^t$ and their top boundaries are inside the region. In Fig. 9(b), we give a schematic diagram of the clause rectangles, regions, and positions of the points corresponding to the clauses. We now describe how the rectangles and points corresponding to the clauses interact with the rectangles and points corresponding to variables.

Fig. 9.

(a) Structure of a variable gadget. (b) Position of the rectangles and points (empty ellipses) corresponding to the clauses.

For each variable $x_i$, $1\le i \le n$, sort the vertical connections from left to right that connect to $x_i$ from clauses connecting from above. Let clause $C_t$ connect to $x_i$ via l-th connection, then we say that $C_t$ is the l-th clause for the variable $x_i$. Assume that the clause $C_t$ contains three variables $x_i$, $x_j$, and $x_k$ in this order from left to right. We now have the following cases.

➣:

Here $x_i$ is a left variable in the clause $C_t$ and let $C_t$ be the $l_1$-th clause for $x_i$. If $x_i$ occurs as a positive literal in $C_t$, then we place the point $p^{t_i}$ inside the rectangle $s_{8l_1-5}^i$. Otherwise, we place $p^{t_i}$ inside the rectangle $s_{8l_1-4}^i$.

➣:

Here $x_j$ is a middle variable in the clause $C_t$ and let $C_t$ be the $l_2$-th clause for $x_j$. If $x_j$ occurs as a positive literal in $C_t$, then we place the point $p^{t_j}_1$, $p^{t_j}_2$, $p^{t_j}_3$, and $p^{t_j}_4$ inside the rectangle $s_{8l_2-6}^j$, $s_{8l_2-5}^j$, $s_{8l_2-3}^j$, and $s_{8l_2-2}^j$ respectively. Otherwise, we shift all the points one rectangle to the right.

➣:

Here $x_k$ is a right variable in the clause $C_t$ and let $C_t$ be the $l_3$-th clause for $x_k$. If $x_k$ occurs as a positive literal in $C_t$, then we place the point $p^{t_k}$ inside the rectangle $s_{8l_3-5}^k$. Otherwise, we place $p^{t_k}$ inside the rectangle $s_{8l_3-4}^k$.

Fig. 10.

Structure of a clause gadget and its interaction with variable gadgets.

See Fig. 10 for the above construction. Clearly, the construction described above can be done in polynomial time.

Theorem 5

The DIS-R-ATL problem is $\mathsf {NP}$-hard.

Proof

We prove that formula $\phi$ is satisfiable if and only if there exists a solution to the DIS-R-ATL problem instance ${\mathscr {D}}$ with cost $8\alpha n + m$. Assume that $\phi$ has a satisfying assignment. From the gadget of $x_i$, select the set $H_i^1$ if the $x_i$ is true. Otherwise select the set $H_i^0$. Hence we select a total of $8\alpha n$ rectangles from the variable gadget. Observe that the way we construct the clause gadget, if the clause is satisfied then exactly one of the rectangles corresponding to each clause is selected in an independent set. Hence we get a solution of $8\alpha n + m$ rectangles.

On the other hand, assume that ${\mathscr {D}}$ has a solution with $8\alpha n + m$ rectangles. From the gadget of $x_i$ we select $8\alpha$ rectangles either $H_i^0$ or $H_i^1$. We set $x_i$ to be true if $H_i^1$ is selected otherwise set $x_i$ to be false if $H_i^0$ is selected. We now argue that this is a satisfying assignment of $\phi$ i.e., every clause is satisfied. Consider a clause $C_t=(x_i\vee x_j\vee x_k)$ (a similar argument can be applied for other clauses as well). If $C_t$ is not satisfied, then we select the sets $H_i^0$, $H_j^0$, and $H_k^0$ from the corresponding variable gadget. These rectangles prevent in selecting any rectangle from the set of rectangles corresponding to $C_t$. This contradicts the fact that the size of the solution is $8\alpha n + m$. However if one of $H_i^1$, $H_j^1$, and $H_k^1$ is selected then from the set of rectangles of $C_t$, exactly one rectangle is selected in a solution. Therefore, the above assignment is a satisfying assignment.    $\square$

3.3 Rectangles Stabbed by a Horizontal Line

We prove that the DIS-R-SHL problem is $\mathsf {NP}$-hard. The reduction is from the R-P-3-SAT problem and is a composition of the two reductions in Sects. 3.2 and 2.3. The way the gadget in Figure 8 is constructed from the gadget in Fig. 5, the similar way we construct the variable gadget here from the gadget in Fig. 9(a). See Fig. 11(a) for the structure of a variable gadget. Clearly, Observation 1 is true for any variable gadget.

The clause gadgets are exactly the same as the clause gadgets in Sect. 3.2. However here the interaction between the clause gadgets and the variable gadgets is different. We first reverse the connection of the clauses in the R-P-3-SAT problem instance i.e., the clauses those connect the variables from above (resp below) are now connect the variables from below (resp above). Now observe that the description of the variable clause connection for the clauses that connects to the variable from above in Sect. 3.2 are true here for the variable clause connection for the clauses that connects to the variable from below. In Fig. 11(b), we give a schematic diagram of the clause rectangle and position of the points corresponding to the clauses. Hence a proof similar to the proof of Theorem 5 concludes:

Fig. 11.

(a) Structure of a variable gadget. (b) Schematic diagram of the variable and clause gadgets and their interaction.

Theorem 6

The DIS-R-SHL problem is $\mathsf {NP}$-hard.