Find a point covered by most sensors

I know of the classic coverage problem, that is, given a set of points, find minimal number of sensors to cover them. It is very applicable and well-researched, and in general case it is NP-hard.

I was wondering about the other direction: given a set of sensors, position n points such that they are covered by most sensors. Is this generally also NP-hard? Are there any known greedy algorithms or some simplifications that make it easier to solve?

To be more concrete, take n=1, assume everything lies on the Euclidean plane, and that all sensors cover disc of the same radius r.

https://stackoverflow.com/questions/66513087/find-a-point-covered-by-most-sensors March 07, 2021 at 12:06PM