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.


  • $\begingroup$ @mvw: I rewrite the question for more clarification. $\endgroup$ – Arnold Jun 27 '15 at 10:28
  • $\begingroup$ What operation is $S_i/S_j$? $\endgroup$ – mvw Jun 27 '15 at 10:38
  • $\begingroup$ @mvw: difference operation: items in $S_i$ but not in $S_j$ $\endgroup$ – Arnold Jun 27 '15 at 11:30

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.)



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.