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$
1

1 Answer 1

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$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .