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)?
2026-03-26 04:49:39.1774500579
Is this coverage problem NP-hard?
186 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
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.