Consider a set of K sensors which have a sensing disc of fixed diameter. We can put sensors on any point within the area. We are interested to deploy all these sensors in an area $A$, such that the total covered area is maximized. Can we say this problem is NP-hard/NP-complete by using NP-completeness of Maximum Coverage Problem (https://en.wikipedia.org/wiki/Maximum_coverage_problem)?
Asked
Active
Viewed 185 times
0
-
maybe this page on tessellation is more appropriate ; a regular tessellation with the same motif is not hard unless you introduce constrains – Sep 21 '16 at 04:14
-
By Theorem 1.2, for fixed K, that will be in NC. Also, see the Covering section of Erich's packing center. – Sep 23 '16 at 18:35
1 Answers
1
How are you specifying the region $A$? How do you specify the point where you put a sensor? Without more details on how you make this a discrete problem, I don't think "NP-hard" or "NP-complete" are applicable. In any case, the Maximum coverage problem you referenced is a discrete graph-theory problem, and it's not at all clear that these can be reduced to your problem of covering by discs, so NP-completeness of Maximum coverage does not say that this problem is NP-hard or NP-complete.
Robert Israel
- 448,999
-
Region A for example can be a square. Sensors are allowed to move to any point on A. – ladan Sep 21 '16 at 13:10
-
Do you know how can I prove NP-hardness when dealing with continuous problems? – ladan Sep 21 '16 at 13:20
-
1"For example" is not enough. You have to specify exactly what regions are allowed. – Robert Israel Sep 21 '16 at 15:25