Point Set Isolation Using Unit Disks is NP-complete

Rainer Penninger, Ivo Vigan

We consider the situation where one is given a set S of points in the plane and a collection D of unit disks embedded in the plane. We show that finding a minimum cardinality subse…