List all sets of points in a plane that are enclosed by circles with given radius

Question

My problem is: Given N points in a plane and a number R, list/enumerate all subsets of points, where points in each subset are enclosed by a circle with radius of R. Two subsets $S_i$ and $S_j$ should be different and not covered each other, i.e. $S_i/S_j \neq \emptyset$ and $S_j/S_i \neq \emptyset$.

Efficiency may not be much important, but the algorithm should not be too slow.

In a special case, can we find K subsets with most points? Approximation algorithm can be accepted.

Thanks,

Answer 1

This does not answer your query, but instead shows that questions within the same intellectual neighborhood can be intricate.

Theorem. Every point set of 12 points can be covered by disjoint unit disks.

Aloupis, Greg, Robert A. Hearn, Hirokazu Iwasawa, and Ryuhei Uehara. "Covering Points with Disjoint Unit Disks." In CCCG, pp. 41-46. 2012. (PDF download.)

---

         

---