1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

Your problem is an instance of a geometric cover problem. Specifically, it appears to be very close to the discrete unit disc cover problem (just scale down all distances by a factor of $d$), which is apparently NP-hard but also admits reasonable approximation algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.