3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.