# Number of point subsets that can be covered by a disk

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

-
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. – Mark Bennet Oct 24 '11 at 20:06
@MarkBennet: Yes, that’s correct. – David Bevan Oct 24 '11 at 20:54
So you put it clearly enough for me to understand, then – Mark Bennet Oct 24 '11 at 21:23
$\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. – Angela Richardson Oct 25 '11 at 6:29
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. – Gerry Myerson Oct 25 '11 at 21:34

By the following argument, the increase in the number of coverable subsets when one more point is added to $n$ points is $\frac12\left(n^2+n+2\right)$, and the claim then follows by induction.

The argument consists of two parts: Counting the increase in the number of coverable subsets when an arbitrarily distant point is added, and showing that the number of coverable subsets doesn't change if points are moved.

Given $n$ points, we can choose the additional point far enough away that all the existing coverable subsets remain coverable. Thus, in this case the increase in the number of coverable subsets is given by the number of coverable subsets containing the new point. Since the new point can be chosen arbitrarily far away, the disks are effectively half-planes, so we're looking for the number of subsets including the new point coverable by a half-plane. Since these subsets correspond bijectively to partitions of the $n+1$ points into two subsets by a line, we need the number of such partitions. This is known to be

$$\binom n0+\binom n1+\binom n2=1+n+\frac{n(n-1)}2=\frac{n^2+2+n}2\;.$$

It remains to be shown that the number of coverable subsets doesn't change if points are moved. The number of coverable subsets could only change if a point is moved across a circle defined by three other points, since at all other positions existing disks can be adjusted to accommodate the movement; it takes three points to create an obstruction to such adjustments.

So consider which subsets become coverable or uncoverable when a point $x$ moves across a circle defined by three points $p$, $q$, $r$. Let's say $x$ crosses the arc of the circle that lies between $p$ and $q$, and let $A$ be the set of points inside the circle. Then the set $A\cup\{r,x\}$ can be covered if $x$ is inside the circle, but not if it is outside, since $p$ and $q$ are in the way. On the other hand, the set $A\cup\{p,q\}$ can be covered if $x$ is outside the circle, but not if it is inside, since excluding $x$ forces the circle to include $r$. These two changes cancel, and the total number of coverable subsets remains invariant.

Considering that the change happens when four points are on a circle and involves the two subsets formed by the points inside the circle with the two pairs of opposing points on the circle, I suspect that there's a nicer way of expressing this that's symmetric with respect to the four points, but I don't have the time to think about that right now – perhaps someone else can add it.

-
Does your argument work if the additional point is on the line determined by 2 of the $n$ points? – Gerry Myerson Oct 26 '11 at 4:38
@Gerry: It doesn't; in fact in that case the assertion is false already for three points, since all non-empty subsets should be coverable but the one containing only the outer two points isn't. I'm aware that I've dealt with the assumptions about general position rather cavalierly and haven't provided many of the details, e.g. for why no other subsets, possibly including proper subsets of $A$, might become (un)coverable. – joriki Oct 26 '11 at 4:55

Here’s a brief outline of the approach I originally took.

The $n\choose 2$ lines that are equidistant from a pair of points partition the plane into $$r_n\;=\;{\!\!{n\choose 2}+1\choose 2}+1-{n\choose 3}$$ regions.

For example, five points gives 46 regions:

$\hspace{1.5in}$

Each region $\mathcal{R}$ defines a permutation $P_\mathcal{R}$ of the points, ordered by their distance from any point in $\mathcal{R}$. Disks centred on a point in $\mathcal{R}$ cover (the points in) some prefix of $P_\mathcal{R}$.

If $\mathcal{R}$ and $\mathcal{S}$ are two adjacent regions, then $P_\mathcal{R}$ and $P_\mathcal{S}$ differ by the reversal of a single pair of adjacent points (e.g. $\ a\dots pq\dots z\$ and $\ a\dots qp\dots z\$). Disks centred on points in $\mathcal{S}$ thus only cover a single subset ($\;a\dots q\;$) of points that is not covered by disks centred on points in $\mathcal{R}$.

This gives us an upper bound of $n+r_n-1$ on the number of coverable subsets: an initial region gives us $n$ subsets; the other $r_n-1$ regions each add at most one further subset.

However, if we consider the permutations corresponding to the regions (in a ‘circuit’) around a point at which (two or three) lines intersect, we see that there is actually one fewer distinct prefix (= coverable subset) for each of the $$i_n\;=\;{\!{n\choose 2}\choose 2}-2{n\choose 3}$$ intersection points. [It is this claim that remains to be proved rigorously.]

Thus we have a total of $n+r_n-1-i_n$ (which is $\frac{n}{6} (n^2 +5)$) coverable subsets.

-
Have you worked out what happens if three of your points are collinear? – Gerry Myerson Oct 26 '11 at 4:39
@GerryMyerson: That’s a good point! I’ve assumed they’re in general position as well as no 4 being concyclic :( – David Bevan Oct 26 '11 at 7:05

When $n=6$, consider four points at the corner of a square, and two more points very close together near the center of the square. To be precise, let's take points at $(\pm1,0)$ and $(0,\pm1)$ and at $(\epsilon,\epsilon)$ and $(-2\epsilon,\epsilon)$ for some small $\epsilon>0$. Then if I'm not mistaken, the number of nonempty subsets that can be covered by a disk is 34 (6 of size 1, 11 of size 2, 8 of size 3, 4 of size 4, 4 of size 5, and 1 of size 6), while your conjectured formula gives 41 [I originally had the incorrect 31].

Now that I think about, when $n=4$, taking two points very near the midpoint of the segment joining the other two points (say $(\pm1,0)$ and $(0,\pm\epsilon)$) gives 12 such nonempty subsets (4 of size 1, 5 of size 2, 2 of size 3, and 1 of size 4) while your conjectured formula gives 14.

Edited to add: it's been commented correctly that the above $n=4$ example does indeed give 14, since every size-3 subset can be covered by a disk. But what about if the four points are $(\pm1,0)$, $(0,\epsilon)$, and $(0,0)$ instead? Now I believe the first three points cannot be covered by a disk without covering the fourth also. Perhaps you want to add the condition that no three points are collinear?

-
Good. But four points at the corners of a square are concyclic, so your $n=6$ case needs some work. – Gerry Myerson Oct 25 '11 at 8:38
@GregMartin: For six points, my formula gives 41, not 31. And you can certainly cover 8 (not 4) different subsets of size 4 in your example. – David Bevan Oct 25 '11 at 9:46
@GregMartin: With your four point example, all four subsets of size 3 can be covered by a disk (very large in two cases) — giving a total of 14 eligible subsets as conjectured. – David Bevan Oct 25 '11 at 9:51
I noted the problem with collinear points in my (last) comment on the original problem. – Gerry Myerson Oct 26 '11 at 0:04