Separating Colored Points with Minimum Number of Rectangles

Navid Assadian Department of Computer Science, University of Victoria [email protected] Sima Hajiaghaei Shanjani Department of Computer Science, University of Victoria [email protected] Alireza Zarei Department of Mathematical Science, Sharif University of Technology [email protected]

(2016)

Abstract

In this paper we study the following problem: Given $k$ disjoint sets of points, $P_{1},\ldots,P_{k}$ on the plane, find a minimum cardinality set $\mathcal{T}$ of arbitrary rectangles such that each rectangle contains points of just one set $P_{i}$ but not the others. We prove the NP-hardness of this problem.

1 Introduction

Let $P=\{P_{1},\ldots,P_{k}\}$ be sets of disjoint points on the plain with $n_{i}=|P_{i}|$ . We say that a rectangle $t$ is $P_{i}$ -rectangle if $t$ contains points from $P_{i}$ and there is no point of $P_{j},j\neq i$ , that lies on the $t$ .

The separation problem on $P$ with arbitrary rectangles can be defined as follows:

Definition ( Minimum Rectangular Separation (MRS):).

Given $P=\{P_{1},\ldots,P_{k}\}$ , find a minimum cardinality set $\mathcal{T}$ of $P_{i}$ -rectangles such that every point in $P$ is contained in at least one rectangle of $\mathcal{T}$ .

Bereg et. al. showed that the Boxes Class Cover problem, a version of MRS, where the rectangles are axis-aligned is NP-hard [1]. They also provide approximation algorithms for some special cases of the problem, for example when the rectangles are axis-aligned squares.

We show the MRS problem is NP-hard for $k=2$ . This implies that MRS is NP-hard for any $k\geq 2$ . We call this version of the problem, MRS for $k=2$ , Arbitrary Boxes Class Cover problem (ABCC). As this can bee seen as a variant of BCC where rectangles can be in any direction.

Bereg et. al showed that BCC-problem is NP-hard by a reduction from the the Rectilinear Polygon Covering problem [1]. This reduction cannot be used to prove the NP-hardness of ABCC. Here we show the NP-hardness of ABCC by a reduction from newly defined version of the 3-SAT problem, the NAS-SAT problem.

1.1 Outline

In section 2, we define a new version of the 3-SAT problem (the NAS-SAT problem), and we prove this problems is NP-hard.

In Section 3, we prove the NP-hardness of BCC by a reduction from the NAS-SAT problem. Then we show how we can modify this and show the NP-hardness of ABCC-problem.

2 NAS-SAT

Not All the Same Satisfication problem (NAS-SAT problem):

We say that a boolean formula $\phi$ is in the form of NAS-CNF if it has the following properties:

1.

$\phi$ is in CNF form.
2.

All of its clauses has at most 3 literals.
3.

All the clauses with more than one literal have at least one literal in negated form and one literal in non-negated form.
4.

Any literal appears in at most one clause of size 3.

The satisfication problem on NAS-CNF formulas is called NAS-SAT.

Theorem 2.1.

NAS-SAT is NP-Complete.

Proof.

NAS-SAT is in NP, as for any given truth assignment the value of the formula cna be computed in polynomial time.

To show the NP-hardness of the problem, we reduce 3-SAT problem to NAS-SAT.

Suppose that an instance $\phi$ of 3-SAT is given. By the following transformations, we transform $\phi$ in polynomial time to $\phi_{NAS}$ which is an instance of NAS-SAT.

For every clause $c_{i}\in\phi$ in form of $c_{i}=(x\vee y\vee z)$ add the following clauses to $\phi_{NAS}$ :

	$\displaystyle(x\vee y\vee z)\equiv(x\vee y\vee{\bar{w}}_{i})\wedge(w_{i}\vee z)\wedge(\bar{w}_{i}\vee\bar{z})$
	$\displaystyle\equiv(x\vee y\vee{\bar{w}}_{i})\wedge(w_{i}\vee z\vee False)\wedge({\bar{w}}_{i}\vee\bar{z}\vee False)$
	$\displaystyle\equiv(x\vee y\vee{\bar{w}}_{i})\wedge(w_{i}\vee z\vee\bar{T})\wedge(T)\wedge({\bar{w}}_{i}\vee\bar{z}\vee F)\wedge(\bar{F})$

For every clause $c_{i}\in\phi$ in form of $c_{i}=(\bar{x}\vee\bar{y}\vee\bar{z})$ add the following clauses to $\phi_{NAS}$ :

	$\displaystyle(\bar{x}\vee\bar{y}\vee\bar{z})\equiv(\bar{x}\vee\bar{y}\vee w_{j})\wedge(w_{j}\vee z)\wedge(\bar{w}_{j}\vee\bar{z})$
	$\displaystyle\equiv(\bar{x}\vee\bar{y}\vee w_{j})\wedge(w_{j}\vee z\vee False)\wedge({\bar{w}}_{j}\vee\bar{z}\vee False)$
	$\displaystyle\equiv(\bar{x}\vee\bar{y}\vee w_{j})\wedge(w_{j}\vee z\vee\bar{T})\wedge(T)\wedge({\bar{w}}_{j}\vee\bar{z}\vee F)\wedge(\bar{F})$

3.

Add other clauses to $\phi_{NAS}$ .
4.

For every variable in $\phi_{NAS}$ that is appeared in more than one clause of size three, we replace them by the following instruction:

Suppose that the variable $x_{i}$ is appeared in $t$ different clauses. Therefore we replace them with new variables $x_{i_{1}},\dots,x_{i_{t}}$ . For preserving the equivalence of these variables, for every $1<k\leq t$ , we insert the following clauses:

$(x_{i_{1}}\vee\bar{x_{i_{k}}})\wedge(\bar{x_{i_{1}}}\vee x_{i_{k}})$

$\phi_{NAS}$ is a CNF formula and every clause has at most 3 literals. By the first and second transformations, the third condition of the NAS-SAT problem is satisfied. By the last transformation, the forth condition is also satisfied. Thus, $\phi_{NAS}$ is an instance of NAS-SAT.

This transformation is done in polynomial time. Therefore, for every instance of the 3-SAT problem, we can construct an instance of NAS-SAT problem in polynomial time which the satisfibility of both of them are equivalent. 3-SAT is NP-hard [2]. Thus, the NAS-SAT problem is NP-complete.

∎

3 ABCC

In the rest of this paper, we assume that $B:=P_{1}$ is the set of blue points, $R:=P_{2}$ is the set of red points, and $n:=n_{1}=|B|$ . Therefore in ABCC the goal is to cover all the blue points and no red point with minimum number of rectangles.

First we show BCC is NP-hard, then we modify the reduction for ABCC problem.

3.1 BCC

Suppose that we have an instance of the NAS-SAT problem, a boolean formula $\phi$ . For every variable, we add some points as shown in the figure 1. In the figures, circles indicate blue points, and stars indicate red points. We call the points added in this step, Variable Points.

Refer to caption — Figure 1: Variable points for all the variables. Circles indicate blue points, and stars indicate red points.

In this structure, points from one variable with points from another variable cannot be covered with a same axis-aligned rectangle. For the points in figure 1, we have $2^{\frac{n}{4}}$ different optimal solutions in the BCC problem As in an optimal solution the variable points of each variable can be covered either with the two horizontal or the two vertical rectangles covering these points. We want to use this idea of having exponential possible solutions to reduce NAS-SAT to BCC.

For every clause, depending on the form of the clause we add different points. The position of these points are described below.

•

For every clause of size one in the form of $c_{i}=x_{i}$ , we add a blue point exactly in the middle of the segment that connects the two leftmost variable points of $x_{i}$ , and we add two red points as shown in the Figure 2. We call the points added in this step equivalent points for $c_{i}$ .

Figure 2: The equivalence points for $c_{i}=x_{i}$
•

For every clause of size in the form of $c_{i}=\bar{x_{i}}$ , we add a blue point exactly in the middle of the segment that connects the two lower variable points of $x_{i}$ , and we add two red points on its sides as shown in the Figure 3. We call the points added in this step equivalent points for $c_{i}$ .

Figure 3: The equivalence points for $c_{i}=\bar{x_{i}}$
•

For every clause of size two in the form of $c_{i}=x_{j}\vee\bar{x_{l}}$ , we add a blue point in the intersection of a vertical line that connects the two leftmost variable points of $x_{j}$ and a horizontal line that connects the two lower variable points of $x_{l}$ . Then, we add four red points around it as shown in Figure 4. These points are called equivalence points for $c_{i}$ .

Figure 4: The equivalence points for $c_{i}=x_{j}\vee\bar{x_{l}}$
•

For every clause of size three in the form of $c_{i}=x_{j}\vee\bar{x_{k}}\vee\bar{x_{l}}$ , we add two blue points as follows:

Assume the two vertical rectangles (strips) that cover variable points of $x_{j}$ and the two upper horizontal rectangles that cover the variable points of $x_{k}$ and $x_{l}$ . We add a blue point in the intersection region between the leftmost rectangle of $x_{j}$ and the upper horizontal rectangle of $x_{k}$ . We also add a point in the intersection region between the rightmost rectangle of $x_{j}$ and the upper horizontal rectangle of $x_{l}$ . The position of these points are shown in Figure 5. We call these points the clause points for $c_{i}$ .

Then, assume the region which is defined by the intersection of the upper rectangle of the red points which are between the upper rectangles of $x_{l}$ and $x_{k}$ , and the leftmost rectangle of the red points which are placed on the right side of the leftmost rectangle of $x_{j}$ . We add a blue point in the upper left corner and a red point in the lower right corner of this region. The position of these points are shown in Figure 5. We call these points the helping points.

Note that, a single blue-rectangle cannot cover the blue helping point and clause points together.

Figure 5: The clause points and helping points for $c_{i}=x_{j}\vee\bar{x_{k}}\vee\bar{x_{l}}$
•

For every clause of size 3 in the form of $c_{i}=\bar{x_{j}}\vee x_{k}\vee x_{l}$ , We add points to the similar places described in the previous part, but with a $\pi/2$ rotation as shown Figure 6.

Figure 6: The clause points and helping points for $c_{i}=\bar{x_{j}}\vee x_{k}\vee x_{l}$

To convert any solution for BCC to a solution for NAS-SAT, for any variable $x_{i}$ , if the blue variable points of $x_{i}$ are covered by the vertical rectangles in the solution for BCC, then we assign $x_{i}$ to ‘true’ in the truth assignment for $\phi$ . If the blue variable points of $x_{i}$ are covered by the horizontal rectangles, then we assign $x_{i}$ to ‘false’ in the truth assignment for $\phi$ .

To convert any solution for NAS-SAT to a solution for BCC, for any variable $x_{i}$ , if $x_{i}$ is assigned to ‘true’ in $\phi$ , then we add two vertical rectangles to the solution for BCC to cover all the blue variable points for $x_{i}$ . If $x_{i}$ is assigned to ‘false’ in $\phi$ , then we add two horizontal rectangles to the solution for BCC to cover all the blue variable points for $x_{i}$ .

Lemma 3.1.

All the blue points can be covered by $2n+m$ blue-rectangles if and only if $\phi$ is satisfiable, where $n$ is the number of variables and $m$ is number of clauses of size three in $\Phi$ .

Proof.

For proving this claim, we have to prove following propositions:

1.

For covering all the blue points, at least $2n+m$ blue-rectangles is needed.
2.

If the blue points are covered by exactly $2n+m$ blue-rectangles in an optimal solution for BCC, then $\phi$ is satisfiable.
3.

If the blue points are covered by more than $2n+m$ blue-rectangles in any optimal solution for BCC, then $\phi$ is not satisfiable.

Proof of 1. To cover all the blue points in this instance of BCC, we need at least two rectangles for each variable. This is because no blue-rectangle can cover the blue variable points of two different variables together. To any blue helping points we need at least one rectangle, as no blue-rectangle can cover two of these helping points or a blue helping point and a blue variable point. There are $n$ variables and $m$ helping points. Thus, covering all the blue points needs at least $2n+m$ rectangles.

Proof of 2. By the previous part we know that $2n+m$ rectangles are needed. If the blue points in BCC are all covered by $2n+m$ rectangles, this means no extra rectangle was used to cover the clause points and equivalence points. This means the two vertical or horizontal rectangles for each variable are compatible with the form of the clauses, and when we convert this solution with $2n+m$ rectangles to a truth assignment for $\phi$ all the clauses of $\phi$ are satisfied by this truth assignment.

Proof of 3. Assume $\phi$ is satisfiable, then we could convert this truth assignment for $\Phi$ to a solution for BCC. This solution for BCC cannot have more than $2n+m$ rectangles. This is because all the variable points are covered by either the two horizontal or the two vertical rectangles. All the blue clause points are covered as the clauses are satisfied by this assignment. All th equivalence points are covered, as or any equivalent clauses at least on of its literals is true in $\phi$ . This means the rectangles for the corresponding literal covers the blue point of that equivalence clause. Thus, only $m$ more rectangles are needed to cover all the blue points. This is a contradiction as we assumed that the any optimal solution for this instance of BCC needs more than $2n+m$ rectangles.

∎

By Lemma 3.1 this transformation is a reduction, and the transformation is polynomial time. Thus BCC is NP-hard.

3.2 Hardness of ABCC

The idea of the reduction from NAS-SAT to ABCC is similar to the reduction from NAS-SAT to BCC. We add the same points described in the previous section for BCC, then we add more red points to the point set in a way that the rectangles in a solution for this instance of ABCC be all axis-aligned rectangles.

For every blue equivalence point, we add red points around it in any direction that there is a blue point in that direction.

For every blue variable point or blue clause point, we add a red point in the intersection between the line that connects it to another blue point and the nearest red strip but not in any blue strip. Note that such region always exists.

We add $O(n^{2})$ new red points in polynomial time. In this structure no arbitrary rectangle can cover two blue points that cannot be covered in the reduction from NAS-SAT to BCC. Thus, the size of the solution for this structure is equal to the size of the solution for BCC in the previous stucture. Therefore, ABCC problem is NP-hard.

References

[1] S. Bereg, S. Cabello, J.M. Díaz-Báñez, P. Pérez-Lantero, C. Seara, I. Ventura. The class cover problem with boxes, Computational Geometry, Volume 45, Issue 7, August 2012, Pages 294-304, ISSN 0925-7721
[2] R. M. Karp Reducibility Among Combinatorial Problems Proceedings of a symposium on the Complexity of Computer Computations, 1972 10.1007/978-1-4684-2001-2_9