Number of point subsets that can be covered by a disk

Question

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

Answer 1

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?

Answer 2

Your conjecture is correct.

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.

Answer 3

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.