Intersections of circles drawn on vertices of regular polygons

Solution 1:

We can find an upper bound by considering the case $n \to \infty :$ There are $\left \lfloor \frac{n}2 \right \rfloor \leq \frac{n}2$ radii. Let the distance between the points be $1$, every circle with radius $k$ has two unique intersections with $1+2(k-1)$ circles with the same radius so in total

$$2n \sum_{k=1}^{n/2} 1+2(k-1) = \frac{n^3}2$$

Every circle with radius $k$ has four unique intersections with $1+2(k-1)$ circles for every bigger radius:

$$4n \sum_{k=1}^{n/2} \bigl( 1+2(k-1) \bigr) \left( \frac{n}2 - k \right) = \frac{n^2}6 (n-1)(n-2)$$

In order to not overcount the starting points we consider them seperately. The upper bound is shown below as well as the fit $a(n) \approx 0.089 \, n^{4.14}$

$$a(n) \leq n + \frac{n^3}2 + \frac{n^2}6 (n-1)(n-2) = n + \frac{n^2}3 + \frac{n^4}6$$

$\hspace{1cm}$