10
$\begingroup$

Using only a compass, draw all possible circles on the vertices of a regular $n$-sided polygon.

(That is, in every ordered pair of vertices one is the center, and their distance is the radius.)

How many intersections are there?

Let $a(n)$ be the intersection count for given $n\in\mathbb N$.

First three terms $a(1),a(2),a(3)=0,2,6$ are simple. The next three terms are:

enter image description here

Notice that the circle set (given by a $n$-sided polygon) can be split into $n$ symmetric regions.

Let $A_n$ count intersections inside one of the $n$ regions. Let $\delta_n\in\{0,1\}$ compensate for when there is one extra central intersection. This implies we can write every term as:

$$a(n)=nA_n+\delta_n$$

The first $20$ terms should be (constructed in GeoGebra):

$$\begin{array}{} a(1) &= \space\space0 &= \space\space1\cdot0 \\ a(2) &= \space\space2 &= \space\space2\cdot1 \\ a(3) &= \space\space6 &= \space\space3\cdot2 \\ a(4) &= 40 &= \space\space4\cdot10 \\ a(5) &= 55 &= \space\space5\cdot11 \\ a(6) &= 145&= \space\space6\cdot24 + 1 \\ a(7) &= 238&= \space\space7\cdot34 \\ a(8) &= 584&= \space\space8\cdot73 \\ a(9) &= 612&= \space\space9\cdot68 \\ a(10) &= 1350&= 10\cdot135 \\ a(11) &= 1804&= 11\cdot164 \\ a(12) &= 2401&= 12\cdot200+1 \\ a(13) &= 3523&= 13\cdot271 \\ a(14) &= 5180&= 14\cdot370 \\ a(15) &= 6150&= 15\cdot410 \\ a(16) &= 9312&= 16\cdot582 \\ a(17) &= 11101&= 17\cdot653 \\ a(18) &= 13645&= 18\cdot758+1 \\ a(19) &= 17746&= 19\cdot934 \\ a(20) &= 22300&= 20\cdot1115 \\ \dots \end{array}$$

We can notice that it seems $\delta_n=1$ if and only if $n$ is a multiple of $6$.

Are there any other patterns? Is it possible to find a closed form for $a(n)$?


My attempt:

WLOG, Let $V_1,V_2,\dots,V_n$ be vertices of a regular $n$-sided polygon with circumradius $1$.

We can take $V_i=(x_i,y_i)=(\cos(\frac{2i\pi}{n}),\sin(\frac{2i\pi}{n})),i=1,2,\dots,n$.

The $k$-th diagonal from some vertex $V$ of the polygon will have length $2\sin(\frac{k\pi}{n})$.

At each vertex $V$, we will have $c=1,2,\dots,\left\lfloor\frac{n}{2}\right\rfloor$ circles$^{[1]}$ with radii $r_c=2\sin(\frac{c\pi}{n})$.

$$ (i,c)\text{-Circle}\dots\space\space \left(x-\cos\frac{2i\pi}{n}\right)^2+\left(y-\sin\frac{2i\pi}{n}\right)^2=\left(2\sin\frac{c\pi}{n}\right)^2 $$

Is it possible to derive a closed form for the number of intersections from this?

I believe I managed to solve a simpler problem:

"At each vertex $V$, consider only one circle of radius $r$."

Then the number of such intersections $I(n,r)$ should be:

$$ I(n,r)=\begin{cases} (n-1)n, & r \gt 1\\ (n-1)n - n\left\lfloor\frac{n}{2}\right\rfloor+1, & r=1\\ (n-2)n, & \sin(\frac{\left(\frac{n}{2}-1\right)\pi}{n})\lt r\lt\sin(\frac{\pi}{2})=1\\ (n-3)n, & r = \sin(\frac{\left(\frac{n}{2}-1\right)\pi}{n})\\ \dots & \dots \\ (2k)n, & \sin(\frac{k\pi}{n}) \lt r \lt \sin(\frac{(k+1)\pi}{n})\\ (2k-1)n, & r = \sin(\frac{k\pi}{n})\\ \dots & \dots \\ 4n, & \sin(\frac{2\pi}{n}) \lt r \lt \sin(\frac{3\pi}{n})\\ 3n, & r = \sin(\frac{2\pi}{n})\\ 2n, & \sin(\frac{\pi}{n}) \lt r \lt \sin(\frac{2\pi}{n})\\ 1n, & r = \sin(\frac{\pi}{n})\\ 0, & r \lt \sin(\frac{\pi}{n}) \end{cases} $$

This solves the problem of intersections for any $r\in\mathbb R_{+}$ but for only one layer of circles.

In the original problem, we have $\left\lfloor\frac{n}{2}\right\rfloor$ layers of circles with different radii on each layer. The radii of circles between layers have specific ratios (determined by $n$): radii are diagonals of the regular $n$-sided polygon.

My idea was to use $I(n,r_c),c=1,2,\dots,\left\lfloor\frac{n}{2}\right\rfloor$ to get to $a(n)$. But, I get lost when trying to add and subtract all of the unique and duplicate intersections.

How can we solve the original problem and find $a(n)$?

$\endgroup$
3
  • $\begingroup$ 4 sets of 3 rings in the 4, 5 sets of 4 rings in the 5, etc. $\endgroup$
    – user645636
    Jan 24 '20 at 15:27
  • $\begingroup$ each pair of annuli have 8 intersection points encompassing the two intersections. $\endgroup$
    – user645636
    Jan 24 '20 at 15:53
  • $\begingroup$ Quick note: Someone made an OEIS sequence for this- oeis.org/A331702. It's attributed to this exact MSE question. $\endgroup$ Aug 31 '21 at 22:56
1
$\begingroup$

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

$\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.