MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is inspired by the recent question about separating unit disks by lines, which I will refer to as the "line case". Replacing "line" by "circle" adds one degree of freedom, and I'm wondering if that changes the asymptotic behaviour. More precisely:

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 $c_n$ be the smallest $d$ such that any such constellation is circle-separable, i.e. that there is a separating circle which has exactly $n$ disks in its interior. It may touch some disks but not intersect them. Like for separating lines, it is easy to see that such a $d$ and thus $c_n$ exists.
I think that again for each $c_n$ there exists a $c_{n'}>c_n$, which should (?) be clear by starting with an extremal constellation $C$ for $c_n$ and adding disks on an appropriately chosen big (but not too big) circle around it. But a priori it is not clear in this case whether the disks can always be chosen in a useful way. For $n$ small (as in the example below, with $n=3$ and $n'=8$), the separating circles are "too small" and thus cannot remain the same for the bigger configuration.
In spite of this potential difficulty in constructing increasing subsequences, and even though the $c_n$'s appear to be much smaller than the $d_n$'s of the line case, I will be more cautious now about conjecturing it, but still feel free to ask:

Is $\{c_n\}$ bounded?

Of course I am wondering if a probabilistic approach will still work here.

As an example, similar to the one I gave for the line case, consider the two constellations for $n=8$: enter image description here

For both constellations, the blue separating circle touches five disks (grey in the right picture), which seems to indicate that both are 'tight', i.e. the displayed proportions are (about) best possible for their respective patterns. Visibly, the right one is better with $h(C)\approx 2.5$. The small green circle (which is circumscribed to the three disks it contains) shows BTW that $c_3$ must be a bit smaller, as the constellation formed by the six central disks (which has the same minimal distance as the entire set) is not circle-separable.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.