5
$\begingroup$

It is easy to show that $n$ (mutually different) circles on the plane can have maximum $n(n-1)$ intersection points. In our optimal graph drawing research we have encountered a counterpart of this result. For a natural number $n$ let $c_3(n)$ denotes the maximum number of triple intersection points of $n$ (mutually different) circles on the plane. (A point is a triple intersection point if in belongs to at least three circles of the family). This problem looks natural and simple, so it should be already known. Thus I tried to google for it. Surprisingly, I found nothing, hence I decided to ask here for a reference.

We can easily show that $c_3(n)\le n(n-1)/3$, by counting intersection points (there are at most $n(n-1)$ of them) taking into account their multiplicity (each triple intersection point needs at least there of them) and maybe the value of $c_3(n)$ is asymptotically close to this upper bound. But for our applications we are mainly interested in upper bounds for small values of $n\le 10$. For instance, the following pictures combined with the above upper bound shows that $c_3(5)=6$, $8\le c_3(6)\le 10$, and $12\le c_3(7)\le 14$.

enter image description here

enter image description here

enter image description here

$\endgroup$
2
$\begingroup$

The following construction shows that $c_3(n)\ge n^2/4-1$. Put $k=\lceil \frac{n+1}2\rceil$ and draw a regular $k$-gon $K$ with side $1$. Initially, we place $k$ black unit circles centered in the corners of $K$. This generates $k - 1$ circular layers of $k$ double intersection points (see, for instance, the last picture at the question). Since $k-1\ge n-k$, we can cover $n-k$ layers by red circles, achieving at least $k$ triple intersection points on each layer and $k(n-k)\ge n^2/4-1$ of them in total.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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