Maximum Centre-Disjoint Mergeable Disks

It is trivial to show that Proper MCMD is in NP. To show that it is NP-hard, we reduce Planar Monotone 3-SAT to Proper MCMD. Let $I$ be an instance of Planar Monotone 3-SAT, with variables $V$ and clauses $C$. Based on Lemma 3.5, there exists a monotone rectilinear representation of $I$ on a $(\left|C\right|+1)\times(3\cdot\left|C\right|+\left|V\right|)$ integer grid. Let $R$ denote this representation.

We create an instance of Proper MCMD from $R$ as follows. The transformation is demonstrated in Figure 8, which corresponds to the monotone rectilinear representation of Figure 5.

1. 1.

   We replace the segment corresponding to a variable in $R$ with an Input gadget and a chain of 2-Copy gadgets. For each intersection of this segment with a vertical segment, a 4-Copy gadget is used.

2. 2.

   Let $s$ be a horizontal segment corresponding to a clause in $R$. Three variables appear in the clause, for each of which there is a vertical segment that connects $s$ to a variable segment. For the first and last intersections, 4-Copy gadgets are used. For the 2nd intersection, we use a Disjunction gadget. These gadgets are connected using two chains of 2-Copy gadgets.

3. 3.

   For each vertical segment that connects a variable segment to a clause segment above the $x$-axis, we use a chain of 2-Copy gadgets to connect the 4-Copy gadget of the variable segment to the 4-Copy or Disjunction gadget (if it is the 2nd intersection) of the clause segment. For segments that appear below the $x$-axis, we do likewise, except that we place a Not gadget before the chain of 2-Copy gadgets.

Note that some of the gadgets of Figure 7 need to be rotated or mirrored, for instance, in the vertical chains that connect clauses and variables. Also note that based on the sizes shown in Figure 7, shared m-disks always appear on grid lines in our construction. Since the distance between the shared m-disks of any of the gadgets is at least 0.25, at most four gadgets can appear on a grid segment of unit length. Given that the total area of the grid, and therefore the total length of grid segments, is bounded by $O(\left|C\right|^{2})$, the number of gadgets used in the resulting instance of Proper MCMD is at most $O(\left|C\right|^{2})$. Thus, the size of the resulting Proper MCMD instance is polynomial in terms of the size of the input Planar Monotone 3-SAT instance.

Suppose there is a proper assignment for our Proper MCMD instance. We obtain an assignment $A$ of the variables of our Planar Monotone 3-SAT instance as follows. We assign one to a variable if the m-disk of its corresponding Input gadget is merged out, and assign zero otherwise. Consider any clause $c$ in our Planar Monotone 3-SAT instance. Let $g$ be the Disjunction gadget corresponding to $c$.

If $c$ is a positive clause, a chain of 2-Copy gadgets connects the Input gadget of each of the variables that appear in $c$ to $g$. Therefore, if variable $v$ appears in the clause and if the shared m-disk of the Input gadget corresponding to $v$ is merged out, the m-disk of the last 2-Copy gadget of its chain is merged in inside $g$. Since, one or more of the shared m-disks of $g$ are merged in, at least one of the literals in $g$ is satisfied. Similarly, if $c$ is a negative clause, because there is a Not gadget in the chain that connects each variable $v$ of $c$ to its Disjunction gadget, if the shared m-disk of the Input gadget corresponding to $v$ is merged out, the m-disk of the last 2-Copy gadget of its chain is also merged out inside $g$. Since, one or more of the shared m-disks of $g$ are merged in, at least one of the variables in $g$ is not satisfied.

Therefore, the Planar Monotone 3-SAT instance is satisfied with assignment $A$.

For the reverse direction, suppose there exists an assignment $A$ of the variables, for which all clauses of $I$ are satisfied. We can obtain a proper assignment in our Proper MCMD instance as follows. For each variable $v$ in $V$, if $v$ is one, the shared m-disk of the Input gadget corresponding to $v$ is merged out, and otherwise, it is merged in. Let $c$ be a positive clause in which variable $v$ with value one appears (since $c$ is satisfied in $A$, variable $v$ must exist), and let $g$ be the disjunction gadget corresponding to clause $c$. Since $v$ is merged out, the m-disk of the last 2-Copy gadget that connects the gadget corresponding to $v$ to $g$ is merged in with respect to $g$. This implies that one of the shared m-disks of the Disjunction gadget of each positive clause is merged in. We can similarly show that at least one of the shared m-disks of the Disjunction gadgets corresponding to negative caluses are also merged in. This yields a proper assignment for the Proper MCMD instance.

We fix the radius of m-disks to $r=0.01$. We use the same construction as Theorem 3.6, with the difference that we replace each s-disk with a number of smaller disks of radius $r$ with the same centre, so that the sum of the radii of these smaller disks equals the radius of the s-disk. Since the disks added for each s-disk are not centre-disjoint, and their centre cannot be contained in some other disk, exactly one of them must be selected and after merging others, it reaches the size of the original s-disk. The rest of the proof of Theorem 3.6 applies without significant changes.

Let $R$ be a monotone rectilinear representation of a Planar Monotone 3-SAT instance (such a representation certainly exists [15]). By extending horizontal segments of $R$ we get at most $c+1$ lines: one for the variables (the $x$-axis) and at most $c$ for clauses. Let $\ell_{1},\ell_{2},\dots,\ell_{m}$ be the lines that appear above the $x$-axis ordered by their $y$-coordinates. We move them (together with the segments appearing on them) so that, $\ell_{i}$ is moved to $y=i$; vertical segments that connect them to a segment on the $x$-axis may need to be shortend or lengthened during the movement. Given that the $x$-coordinate of the end points of horizontal segments, and also the vertical order of the segments, do not change, no new intersection is introduced by this transformation. The same is done for the lines that appear below the $x$-axis.

Repeating the same process for vertical segments, we get at most $3c$ vertical lines. We can similarly move these lines and the segments on them horizontally so that they appear in order and consecutively on vertical integer grid lines. Variables that do not appear in any clause, can be placed in at most $v$ additional vertical grid lines. This results in a $(c+1)\times(3c+v)$ grid.

Let $S$ be the largest subset of $D$ for which there exists a uproper assignment $\phi_{S}$. If $S=D$, we are done; so we assume otherwise. Let $d_{k}$ be any disk in $D\setminus S$. The centre of $d_{k}$ is contained in at least one disk $d_{i}$ of $S$ (considering its aggregate radius); otherwise, $d_{k}$ may be added to $\phi$ as a selected disk, which contradicts the choice of $S$.

We obtain a uproper assignment $\phi_{S^{\prime}}$ for $S^{\prime}=S\cup\{d_{k}\}$ as follows. Initially we set $\phi_{S^{\prime}}(d_{x})=\phi_{S}(d_{x})$ for every $d_{x}\in S$. We also set $\phi_{S^{\prime}}(d_{k})=d_{i}$, as $d_{i}$ contains the centre of $d_{k}$. Merging $d_{k}$ increases the aggregate radius of $d_{i}$. If $\phi_{S^{\prime}}$ is not uproper, $d_{i}$ must contain the centre of another disk $d_{j}$ such that $\phi_{S^{\prime}}(d_{j})=d_{j}$ (it must be a selected disk in $\phi_{S}$). We modify $\phi_{S^{\prime}}$ so that $\phi_{S^{\prime}}(d_{x})=d_{i}$ for every $d_{x}\in\delta_{j}^{\phi}\cup\{d_{j}\}$ (here, with some abuse of notation, assume $\delta_{j}^{\phi}$ to be a set). These changes satisfy the second condition of Definition 3.13: after merging $d_{j}$ with $d_{i}$, $d_{i}$ contains $d_{j}$ completely (because the centre of $d_{j}$ was inside $d_{i}$ before the merge and after it, the aggregate radius of $d_{i}$ is increased by $r_{j}$), and therefore it must contain the centre of $\delta_{j}^{\phi}(1)$. We then merge $\delta_{j}^{\phi}(1)$ with $d_{i}$, then we can merge $\delta_{j}^{\phi}(2)$ with $d_{i}$, and so on.

If, after these changes, $\phi_{S^{\prime}}$ is not uproper, then $d_{i}$ contains the centre of another selected disk $d_{y}$. For every such disk, we similarly merge with $d_{i}$, $d_{y}$ and every disk merged with it, until $d_{i}$ does not contain the centre of any other disk, and then, $\phi_{S^{\prime}}$ becomes proper. This contradicts the choice of $S$ and implies that we have a uproper assignment for $D$.

We reduce Partition to RMCMD. Let $A=\{a_{1},a_{2},\dots,a_{n}\}$ be an instance of Partition and $s$ be the sum of the members of $A$. Also let $e$ be a real number such that $0<e<1$; we use $e$ to create distances smaller than a segment of unit length. We create an instance of RMCMD as follows (see Figure 9).

1. 1.

   Add disk $d_{1}$ of radius $2s$ and add $d_{2}$ with the same radius at distance $3s$ on the right of $d_{1}$.

2. 2.

   Add $d_{3}$ at distance $5s/2+e$ above $d_{1}$ with radius $s$. Similarly, add $d_{4}$ at distance $5s/2+e$ above $d_{2}$ with the same radius.

3. 3.

   Add one disk for each member of $A$ in the midpoint of the centres of $d_{1}$ and $d_{2}$, such that the radius of the one corresponding to $a_{i}$ is $a_{i}$.

Let $\phi$ be the solution of this RMCMD instance. We show that there is a valid solution to the Partition instance if and only if the cardinality of $\phi$ is four.

Suppose $X$ is a subset of $A$ with sum $s/2$. We obtain an assignment from $X$ as follows: every disk corresponding to a member of $X$ is assigned to $d_{1}$ and others are assigned to $d_{2}$. Since the sum of the members of $X$ is $s/2$, the aggregate radii of both disks are exactly $5s/2$. Therefore, the centre of $d_{3}$ and $d_{4}$ are outside these disks. This yields a uproper assignment of cardinality 4.

For the reverse direction, suppose the cardinality of $\phi$ is four (note that it cannot be greater). If so, all of $d_{1}$, $d_{2}$, $d_{3}$, and $d_{4}$ are selected, and therefore, the aggregate radii of $d_{1}$ and $d_{2}$ are lower than $5s/2+e$. Given that the sum of the radii of the disks corresponding to members of $A$ is $s$ (which is an integer) and $0<e<1$, the sum of the set of disks assigned to $d_{1}$ and $d_{2}$ (and therefore the subsets of $A$ corresponding to them) are equal.

For $1\leq i,j\leq n$, we introduce a binary variable $x_{i,j}$. If $i\neq j$, $x_{i,j}$ indicates whether disk $d_{i}$ is merged with disk $d_{j}$. If $i=j$, it shows if disk $d_{i}$ is a selected disk. The following constraint for $1\leq i\leq n$ makes sure that each disk is either selected or merged with another disk.

An assignment $\phi$ can be obtained from the values of variables $x_{i,j}$ by letting $\phi(d_{i})=d_{j}$ if and only if $x_{i,j}=1$.

Based on the conditions enumerated in Definition 2.3, we add additional constraints to make sure that the obtained assignment $\phi$ is proper. Let $\delta_{i}$ be as defined in Definition 2.2.

1. 1.

   Based on the first condition of Definition 2.2, a disk can be merged with $d_{i}$, only if its closer disks are merged as well. In other words, $x_{\delta_{i}(j+1)i}$ can be one, only if $x_{\delta_{i}(j)i}$ is also one for $1\leq j\leq n-2$, as expressed in the following constraint for $1\leq i\leq n$ and $1\leq j\leq n-2$.

   $$x_{\delta_{i}(j)i}\geq x_{\delta{i}(j+1)i}$$

   (2)

2. 2.

   Based on the second condition of Definition 2.2, $d_{j}$ can be merged with $d_{i}$, only if the distance of $d_{i}$ and $d_{j}$ is less than $r_{i}(j-1)$ (Definition 2.2) for $1\leq j\leq n-1$; that is, after merging with $d_{i}$ all disks closer than $d_{j}$ to $d_{i}$, the resulting disk must contain the centre of $d_{j}$. We disallow merges that fail this condition: for $1\leq i\leq n$ and $1\leq j\leq n-k$, where $r_{i}(j-1)<|p_{i}p_{j}|$, we add the following constraint (for simplicity, let $r_{i}(0)=r_{i}$).

   $$x_{ji}=0$$

   (3)

3. 3.

   Based on the third condition of Definition 2.2, selected disks must be centre-disjoint. We add the following constraint for $1\leq i,j\leq n$.

   $$\sum_{k=1}^{n}r_{k}\cdot x_{ki}\leq|p_{i}p_{j}|+\infty\cdot(1-x_{jj})$$

   (4)

   Obviously, the left side computes the aggregate radius of $d_{i}$; note that if $d_{i}$ is not selected, the left side equals zero and the inequality is trivially satisfied. There are two cases based on whether $d_{j}$ is selected or not. If $d_{j}$ is a selected disk ($x_{jj}=1$) the right side of the inequality simplifies to $|p_{i}p_{j}|$, making sure that $d_{i}$ does not contain $d_{j}$. If, on the other hand, $d_{j}$ is merged with another disk (maybe even with $d_{i}$), the right side of the inequality simplifies to $+\infty$ and the constraint is satisfied.

Finally, as the goal of MCMD (Definition 2.4) is to maximize the number of selected disks, the objective of the programme is simply to maximise $\sum_{i=1}^{n}x_{ii}$.

Let $M$ be defined as in Definition 4.4. Obviously, $\max_{i=1}^{n}M(n,i,n)$ is the cardinality of the solution to this MCMD instance.

The function $M$ accepts $O(n^{3})$ different input values. We can compute and store the values returned by $M$ in a three dimensional table, which we reference also as $M$. Algorithm 1 uses dynamic programming to fill $M$, and computes its entries based on the values of previously computed entries. Before explaining the details of the algorithm, we give a high-level overview as follows. The order of the disks referenced here, in the algorithm, and its succeeding discussion is demonstrated in Figure 10.

The main idea behind the algorithm is that in every proper assignment of $\{d_{1},d_{2},\dots,d_{x}\}$, there is at least one selected disk; take the right-most selected disk $d_{i}$. By the first condition of Definition 2.3, for some $j$ where $0\leq j\leq n-1$, the first $j$ entries of $\delta_{i}$ are merged with $d_{i}$. Thus, the algorithm considers different values of $j$ for each disk $d_{i}$, to compute the maximum proper assignment of $\{d_{1},d_{2},\dots,d_{x}\}$ for any $x$ in which $d_{i}$ is the right-most selected disk and $j$ disks are merged with $d_{i}$; it updates the entries of $M$ accordingly. The main challenge is to decide what to do with the disks that appear on the left of $d_{i}$ and use the previously filled entries of $M$ for them. To do so, the algorithm enumerates possible choices for the right-most selected disk $d_{t}$ that appear on the left of $d_{i}$, and the number of disks $k$ merged with it.

After presenting Algorithm 1, we shall explain the steps of this algorithm in more detail.

Steps 1 and 2 of the algorithm initialize $M$ and $\delta_{i}$. In Step 3, we consider different cases in which $d_{i}$, for $1\leq i\leq n$ in order, is selected and update the value of different entries of $M$. For every possible value of $j$ from $0$ to $n-1$, suppose $j$ disks are merged with $d_{i}$. These disks are the first $j$ disks of $\delta_{i}$ by the first condition of Definition 2.3.

Let $S$ denote the set of such disks. If this is not possible (the centre of one of these disks is not contained in $d_{i}$, after merging its previous disks), we skip this value of $j$, because it fails the second condition of Definition 2.3 (Step 3a). Note that if there exists no proper assignment in which $j$ disks are merged with $d_{i}$, there cannot exists a proper assignment in which more than $j$ disks are merged with $d_{i}$ either, and we can safely skip the remaining values of $j$ and continue the loop of Step 3 by incrementing the value of $i$.

Let $a$, $b$, $A$, and $B$ be defined as Step 3b. If $a=1$, selecting $d_{i}$ and merging with it every disk in $\{d_{1},d_{2},\dots,d_{b}\}\setminus\{d_{i}\}$ is a proper assignment of the first $b$ disks of $\lambda$ with cardinality one. Therefore, we update the value of $M(b,i,B)$ to be at least one in Step 3c.

If $a>1$, let $\phi$ be any assignment of $\{d_{1},\dots,d_{b}\}$, in which i) $d_{i}$ is selected, ii) the members of $S$ are merged with $d_{i}$, and iii) the members of $\{d_{A},\dots,d_{a-1}\}\cup\{d_{b+1},\dots,d_{B}\}$ are contained in $d_{i}$ after merging the members of $S$ with $d_{i}$. By the definition of $M$, the value of $M(b,i,B)$ cannot be smaller than the cardinality of $\phi$. When $\phi$ is limited to $L=\{d_{1},\dots,d_{a-1}\}$, it specifies a proper assignment of $L$. We denote this assignment with $\phi_{L}$. We compute the value of $M(b,i,B)$ by considering all possible assignments for $\phi_{L}$ and extending them to obtain $\phi$ by selecting $d_{i}$.

Let $d_{t}$ be the right-most selected disk of $\phi_{L}$. The following conditions hold.

1. 1.

   We have $t<A$, because $\{d_{A},\dots,d_{a-1}\}$ are contained in $d_{i}$ in $\phi$, and $d_{t}$ cannot be a selected disk if $t\geq A$. Therefore, disks $\{d_{t+1},\dots,d_{a-1}\}$ are merged with $d_{t}$ in $\phi_{L}$.

2. 2.

   Suppose $k$ disks are merged with $d_{t}$ in $\phi_{L}$. Let $d_{f}$ be the right-most disk of $D$ contained in $d_{t}$ after merging disks in $\phi_{L}$. We have $f<i$; otherwise, $d_{f}$ would contain the centre of $d_{i}$, and $d_{i}$ cannot be selected in $\phi$. Also let $d_{g}$ be the right-most vertex of $D$ contained in $d_{f}$. We have $g<i$; otherwise, $d_{f}$ would contain the centre of $d_{i}$ and $\phi$ cannot be an extension of $\phi_{L}$.

By trying possible values of $t$ and $k$ that meet these conditions (Step 3d), we find the maximum cardinality of $\phi_{L}$, which has been computed in the previous steps of this algorithm as $M(a-1,t,g)$. Since $\phi$ is an extension of $\phi_{L}$ by adding exactly one selected disk $d_{i}$, the maximum cardinality of $\phi$ therefore is at least $1+M(a-1,t,g)$. Thus, we have

Step 3(d)iv updates $M(b,i,B)$ to be at least this value.

We analyse Algorithm 1. Constructing $\delta_{i}$ (Step 1) can be done in $O(n^{2}\log n)$ and initializing $M$ (Step 2) can be done in $O(n^{3})$. For each pair of values for $i$ and $j$, Steps 3a-3c can be performed in $O(n)$. In Step 3d, $O(n^{2})$ possible cases for $t$ and $k$ are considered, and for each of these cases, the Steps 3(d)i, 3(d)ii, 3(d)iii, and 3(d)iv can be performed in $O(n)$. Since the loop of Step 3 is repeated $O(n^{2})$ times, the time complexity of the whole algorithm is $O(n^{5})$.