6
$\begingroup$

Given $n$ distinct points in the (real) plane, how many distinct non-empty subsets of these points can be covered by some (closed) disk?

I conjecture that if no three points are collinear and no four points are concyclic then there are $\frac{n}{6}(n^2+5)$ distinct non-empty subsets that can be covered by a disk. (I have the outline of an argument, but it needs more work. See my answer below.)

Is this conjecture correct? Is there a good BOOK proof?

This question is rather simpler than the related unit disk question. The answer to this question provides an upper bound to the unit disk question (for $k=1$).

  • 0
    I don't think it is quite clear what you mean. Would this be a correct interpretation? The $n$ points are on a real plane. If you take a ?closed disk with any centre and radius, it will cover a subset of the points. If it contains at least one point it defines an eligible subset of the points. Different disks with different centres and radii may define the same eligible subset. You are interested in the number of different eligible subsets you can obtain in this way.2011-10-24
  • 0
    @MarkBennet: Yes, that’s correct.2011-10-24
  • 0
    So you put it clearly enough for me to understand, then2011-10-24
  • 0
    Your conjecture can't be the exact number (since it isn't always an integer), so do you mean it as an upper bound? a lower bound? an asymptotic bound?2011-10-24
  • 0
    Can you calculate the number for small values of $n$ and then look it up in the Online Encyclopedia of Integer Sequences?2011-10-25
  • 1
    $\frac{n}{6}n^{2}+5$ is always an integer. It could be an upper bound. In a convex polygon of n points, a disk can cover each of the n points, each of the n pairs of adjacent points, each of the n triples... so that the number of subsets covered is n(n-1)+1.2011-10-25
  • 0
    @GerryMyerson: If you click on $\frac{n}{6}(n^2+5)$ in the question, it takes you to the relevant _OEIS_ entry.2011-10-25
  • 0
    @GerryMyerson: I intend my conjecture to be exact. I have the outline of an argument, but it needs more work. (I’ll share my approach later.)2011-10-25
  • 0
    @Angela, thanks, I missed that.2011-10-25
  • 1
    I think the "no 4 points concyclic" hypothesis is too weak. I think you also need "no 3 points collinear." Let ABC be collinear, B between A and C, let D be somewhere else. You can't cover A and C without covering B (unless you count a half-plane as a disk of infinite radius), so you miss both AC and ACD and get only 13 instead of 14 subsets.2011-10-25
  • 0
    @Gerry: I think you're right; in fact the problem already occurs for $3$ points, where all non-empty subsets should be coverable but if the points are colinear the subset consisting only of the outer points can't be covered.2011-10-26
  • 0
    @Gerry: Thanks for the observation; I've updated condition in the question.2011-10-26

3 Answers 3