<p>If I arrange the disks into a spiral pattern then the problem is NP-hard. It may be even harder in your general case. This would be a variation on the polygon covering problem.</p>

<p>See <a href="https://en.wikipedia.org/wiki/Polygon_covering" rel="nofollow">https://en.wikipedia.org/wiki/Polygon_covering</a></p>

CC BY-SA 3.0
2015-08-05T20:44:22.263Z
2015-08-05T20:44:22.263Z
Joshua Herman
<p>A reduction from planar 3-SAT should work. At least if the disks need not have equal size.</p>

<p>Start by creating a triangular grid of disks (shown in blue in the figure).
We enforce these disks to be in the cover by not covering one of their points by any other disks.
Now what remains is to cover the gaps left in between disks by a minimal number of disks.</p>

<p>Illustrated are And- and Or-gadgets that can be connected using <em>wires</em> of arbitrary (even) length. Wires are simply a series of disks that each cover two gaps.
<em>Variable</em> gadgets are each a cycle of And-gadgets, where each C-terminal is connected to the A-terminal of the next And-gadget. This creates B-terminals that can each connect to an Or-gadget.
Finally, there may be unused gaps (that are not part of any gadget) which we can simply fill using a single disk.</p>

<p>Then, if there is a solution to an instance of 3-SAT, there is a set $D'$ that for each And-gadget covers either terminal $A$ or $C$, but never both. And in which the gaps that are part of wires are covered exactly once. Hence, such cover is optimal.</p>

<p>Conversely, if no solution exists, some wire needs more disks to cover, or some And-gadget is covered by both terminal $A$ and $C$, requiring a higher cardinality cover.</p>

<p><a href="https://i.sstatic.net/x1Fbv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/x1Fbv.png" alt="And/Or-gadgets"></a></p>

CC BY-SA 3.0
2015-08-05T21:00:47.223Z
2015-08-05T22:57:55.113Z
2015-08-05T22:57:55.113Z
Tim
<p>Given a rectangular region $R$ and a set $D$ of $n$ disks such that the union of all disks in $D$ cover the entire rectangular region $R$, the objective is to find the minimum cardinality set $D'$ subset of $D$ such that the union of all disks in $D'$ cover the entire $R$.
I believe that this problem is NP-hard, but did not find any reference. can somebody help me to find the one or reduction from an NP-hard problem.</p>

<reference-request><np-hardness><computational-geometry>
Is this covering problem NP-hard?
Manju
# Is this covering problem NP-hard?

(Asked by: username_0 on 2015-08-05)

Given a rectangular region $R$ and a set $D$ of $n$ disks such that the union of all disks in $D$ cover the entire rectangular region $R$, the objective is to find the minimum cardinality set $D'$ subset of $D$ such that the union of all disks in $D'$ cover the entire $R$.
I believe that this problem is NP-hard, but did not find any reference. can somebody help me to find the one or reduction from an NP-hard problem.

**Tags:** reference-request, np-hardness, computational-geometry


---

## 2 answers

### Answer by username_1 on 2015-08-05. Score: 1

If I arrange the disks into a spiral pattern then the problem is NP-hard. It may be even harder in your general case. This would be a variation on the polygon covering problem.

See <https://en.wikipedia.org/wiki/Polygon_covering>


---

### Answer by username_2 on 2015-08-05. Score: 1

A reduction from planar 3-SAT should work. At least if the disks need not have equal size.

Start by creating a triangular grid of disks (shown in blue in the figure).
We enforce these disks to be in the cover by not covering one of their points by any other disks.
Now what remains is to cover the gaps left in between disks by a minimal number of disks.

Illustrated are And- and Or-gadgets that can be connected using *wires* of arbitrary (even) length. Wires are simply a series of disks that each cover two gaps.
*Variable* gadgets are each a cycle of And-gadgets, where each C-terminal is connected to the A-terminal of the next And-gadget. This creates B-terminals that can each connect to an Or-gadget.
Finally, there may be unused gaps (that are not part of any gadget) which we can simply fill using a single disk.

Then, if there is a solution to an instance of 3-SAT, there is a set $D'$ that for each And-gadget covers either terminal $A$ or $C$, but never both. And in which the gaps that are part of wires are covered exactly once. Hence, such cover is optimal.

Conversely, if no solution exists, some wire needs more disks to cover, or some And-gadget is covered by both terminal $A$ and $C$, requiring a higher cardinality cover.

[![And/Or-gadgets](https://i.sstatic.net/x1Fbv.png)](https://i.sstatic.net/x1Fbv.png)


---

