NP completeness proof of sensor selection problem
-
05-11-2019 - |
Question
There are $n$ points in a plane.
The decision problem is to identify whether there exists a set $S$ of $k$ or less points from the $n$ points such that all $n$ points are at most $d$ distance from the selected set of points.
I am trying to use the sensor coverage problem where the idea is to place sensors in the plane where all $n$ points are reached. However, it allows the sensors to be placed at non-$n$ points which my problem doesn't allow. Is there some way I can still show that the problem is NP-complete by subset selection or any other approach.
Thanks!
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange