7
$\begingroup$

Given $n\ge 2$. For a real $d>2$, consider a constellation $C$ of $2n$ disks of radius $1$ in the plane such that $h(C)$, the minimal distance between any two of their centers, is equal to $d$. Let $d_n$ be the smallest $d$ such that any such constellation is separable, i.e. that there is a line which has $n$ disks on either side of it. We'll call such lines separating lines. They may touch some disks but not intersect them. (It is easy to see that such a $d$ and thus $d_n$ exists, by using a different scaling: Choose $2n$ points as centers, start with very small disks and increase the common radius of the disks as much as possible without destroying the separability. Then rescale to radius 1.)

Denote by $\mathcal C_n$ the set of all separable constellations of $2n$ unit disks. Let's call a $C\in\mathcal C_n$ tight if each separating line touches at least three of the disks. Obviously, an extremal $C\in\mathcal C_n$ (i.e. such that $h(C)=d_n$) must be tight, and so we have the equivalent definition $d_n=\max \{h(C): C\in\mathcal C_n \text{ is tight}\}$.

A tight constellation must have a somewhat high degree of symmetry, presumably a $s$-fold rotational symmetry for some $s\ge3$. If there is a disk at the center (and thus $s$ odd), $C$ seems to be much "better" (i.e. closer to extremal) than if not.
A trivial lower bound for $n\ge 4$ is $d_n\ge8\cos\frac\pi{4n-2}$, attained for a constellation $C$ that has one disk at the center and the others forming a regular $(2n-1)$-gon around it.
For $n=2,3$, the same construction is extremal and yields $d_n=2\csc\frac\pi{4n-2}$ (note that for $n\le 3$, $h(C)$ is the circumradius of the $(2n-1)$-gon, whereas for $n\ge4$ it's its side). The image shows the $n=3$ case with $h(C)\approx 6.472$ and the $n=8$ case with $h(C)\approx 7.956$.

5-gon and 15-gon

I'd conjecture that if $2n-1$ is prime, this is best possible. So:

Is it true that $\liminf\limits_{n\to\infty}\ d_n=8$?

Now there are other tight constellations, which may be better for certain values of $n$, e.g. for $n=8$ the following, where 2 of the 10 separating lines are also drawn:
alternate construction for n=8
I haven't calculated this one exactly, but $h(C)$ appears to be slightly bigger than $8$.

Note that for each $n$ there is an increasing sequence $d_n<d_{n_1}<d_{n_2}<\cdots$ because for each extremal constellation $C$, we can imagine an additional concentric circle, sufficiently big, and add a number of disks centered on it such that each of the separating lines of $C$ is intersected by one of them. But I think that $\{d_n\}$ is bounded overall, and it even seems like $d_n$ cannot exceed $8$ very much.

So:

What is $\limsup\limits_{n\to\infty}\ d_n$?

EDIT : after David's answer, I've realized now that there is an easy construction showing that $d_n$ is not bounded. For $d$ fixed, take concentric circles of radii $d,2d,3d,\dots$. On each one, place six disks that form a regular hexagon and rotate each hexagon a bit more, in a way that, imagining a light source at the center, all rays are eventually blocked by some disk. This is possible with a finite number of circles because the harmonic series diverges. The resulting pattern is clearly not separable.
If on the $i$-th circle, we take a regular $6i$-gon instead of a hexagon, the disks are almost regularly distributed, forming a pattern like in those round plastic brushes or in a shower head.


More generally now, for a natural $k\ge2$ consider $kn$ unit disks as above. Let $d_{k,n}$ be the smallest $h(C)$ of any constellation $C$ of $kn$ disks such that there is a separating set of $k-1$ parallel lines (i.e. each of the $k$ strips defined by them contains exactly $n$ disks). If $k_1n_1=k_2n_2$ and $k_2$ is a multiple of $k_1$, obviously $d_{k_2,n_2}\ge d_{k_1,n_1}$, and looking at $d_{2,8}=d_8$ above vs. $d_{4,4}$, I'd expect that this inequality is generally strict.

The following example for $k=4,n=2$ features a regular 7-gon, has $h(C)\approx 12.5$, which I would guess is best possible, and shows that no line of a separating set needs to touch more than two disks, some may even float around $-$ yet it is tight in a sense.
So for $k>2$, the search for extremal constellations is much more tricky than for $k=2$, but I think there are good reasons that again, those must have an $s$-fold symmetry.

k=4, n=2

By this type of construction, it is in fact not hard to show that $\liminf\limits_{n\to\infty}\ d_{4,n}\ge 16$ (and conjecturing that for $4n-1$ prime this is again the best possible constellation would mean that equality holds).
For even $k=6,8,...$, $\liminf\limits_{n\to\infty}\ d_{k,n}$ does not seem to increase further, it rather seems to stick at $16$. Very strange. May there be then a universal bound for $d_{k,n}$?

Note that similar constructions for odd $k$ yield much smaller $h(C)$'s, as no separating line touches the central disk, which is where the situation is most tight.

For fixed $k$, what can be said about $\limsup\limits_{n\to\infty}\ d_{k,n}$?

$\endgroup$
1
  • 1
    $\begingroup$ Your diagrams remind me to the old question mathoverflow.net/questions/20558 What is the minimum N for which there exist N points in the plane that cannot be covered by any number of non-overlapping closed unit discs? $\endgroup$ Jan 23, 2014 at 9:23

1 Answer 1

5
$\begingroup$

An earlier version of this answer used a uniformly random point process but that isn't quite good enough (it will lead to a small number of close-together pairs). Here's a patched version using a more complicated random process.

Choose $r=c_1\frac{n}{\log n}$ and $d=c_2\frac{\sqrt{n}}{\log n}$ for constants $c_1$ and $c_2$ to be determined later. We will choose $2n$ points from a disk of radius $r$, centered at the origin, by repeating the following process $n$ times: find a point $p$ within the disk that is at distance at least $d$ from all other points already chosen and from the origin, and add both $p$ and $-p$ to the set.

Any bisector of this set will have to pass near the origin, so to show that the point set is inseparable we need only show that (with high probability) each strip of unit width through the origin is covered by at least one point. We can find a family of $O(r)$ strips of constant width such that each unit-width strip contains one of the members of this family. Each of the strips in the family has an area that is at least a $\frac{\log n}{n}$ fraction of the area of the whole disk. By adjusting $c_1$ and $c_2$ appropriately we can ensure that the area of the $r$-disk covered by $d$-disks around chosen points is less than half the area of the whole $r$-disk, and therefore that at each step one of these strips has probability proportional to $\frac{\log n}{n}$ of being hit. Therefore, the probability that it is hit at least once throughout the whole process is $1-1/n^{c_3}$ where $c_3$ can be made arbitrarily large by adjusting $c_1$ and $c_2$. By making $c_3$ larger than one, we ensure that with high probability all the strips are hit and therefore that the point set is inseparable.

Thus, $d_n$ can grow at least proportionally to $\frac{\sqrt n}{\log n}$, much larger than a constant.

$\endgroup$
7
  • $\begingroup$ I am not very used to probabilistic thinking, completely different from my "high symmetry" approach. You are "probably" (!) right (I guess you mean S should have $2n$ points), but I have a hard time though understanding "So by choosing the constants appropriately, we can ensure that S is not separable with high probability." The only constant I see is the factor of $\frac n{\log n}$. Combining the fact that each strip near the origin has a number of points in it with "each bisector of this subset must pass near the origin" seems too vague for me. ...(cont'd) $\endgroup$
    – Wolfgang
    Jan 23, 2014 at 8:57
  • $\begingroup$ (cont'd) ... Is the idea of "nearness" clear enough? I am not very convinced yet. That is the big downside of probabilistic proofs, that they usually don't give the least hint towards a construction! $\endgroup$
    – Wolfgang
    Jan 23, 2014 at 9:01
  • $\begingroup$ More explicitly, the radius is $c_1\tfrac{n}{\log n}$ for some constant $c$, and the closest pair is $c_2\frac{\sqrt{n}}{(\log n)^{3/2}}$ for another constant $c_2$. It is by adjusting these constants that we make the probabilities of failure polynomially small with a suitably large exponent, large enough to cover the number of distinct events that might fail. $\endgroup$ Jan 23, 2014 at 17:16
  • $\begingroup$ Even after your edit, I have still trouble following. It just looks too hazardous. If my tyre holds the air "with high probability", there is still some place for a tiny hole... and why must all bisectors have less than unit distance from the origin? I also don't understand the $ 1−1/n^{c_3}$ thing. BTW, what qualitative difference does it make if $c_3>1$ or not? In my impression, if $d$ is too big, maybe like $d=10$, the average "density" of the set of disks is just not big enough to hit all potential bisectors, even if restricting only to those through the origin. $\endgroup$
    – Wolfgang
    Jan 23, 2014 at 21:49
  • $\begingroup$ If a configuration of points, selected by some random process has a desired property with high probability (or even nonzero probability), then there exists a configuration that actually does have the property (otherwise the probability would be zero). As for why all bisectors must be within unit distance from the origin: it's possible (though unlikely) for a farther bisector to exist, but if it does then its translate through the origin will also be a bisector, because of the symmetry of the configuration. So if no bisector through the origin exists, then no bisector exists at all. $\endgroup$ Jan 23, 2014 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.