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
scroll top