# How many circles can fit on the perimeter of $N$-gon

Given a regular $$N$$-gon with perimeter $$P$$ and circle with radius $$R$$. How many of these circles can fit on the perimeter of the $$N$$-gon without overlaping?

$$\frac P{2R}$$ will give correct answer if all the circles sit on the vertices and $$2R$$ is the edge length of the $$N$$-gon. But if the edge is longer than $$2R$$ then more than two circles can fit on an edge and there can be vertices where circles cant be placed, because the circles will overlap. This creates a situation where $$K$$ circles are placed on the perimeter, more than $$K$$ cannot be placed without overlaps, and $$K \cdot 2R < P$$. Could it be that $$P - K \cdot 2R > 2R$$ or is it safe to assume that no matter what $$P - K\cdot 2R < 2R$$? Similar situation will happen if $$N$$-gon edge length is less than $$2R$$.

• Are the circles forbidden to overlap only on the perimeter or completely? For example, circles at opposing vertices of a unit square overlap on the perimeter (namely at the other vertices) iff $R>1$, but they overlap in the interior of the square already for $R>\sqrt 2/2$. – Hagen von Eitzen Jun 20 at 7:20
• No overlaps at all. Only thing that is allowed with overlaps is that, if the overlap is very small. less R/2 then you can increase the perimeter just enough to make that overlap disappear. – Marko Taht Jun 20 at 7:26
• What is the source of this question? A textbook exercise? A contest? Your imagination? Is there a known answer that you are trying to find? Or are you exploring an open question? (BTW: Please always edit your question to add clarifying remarks. Comments are easily overlooked.) – Blue Jun 20 at 7:28
• @Blue it is for work. Im working on a GUI solution and we will have lot of circles on screen that have to fit on a N-gon perimeter. There is a condition, that if the amount of circles is too large we need to layer it. Ex. 1 goes to center, next is 6. So if the circle count goest to 7 we need these 2 layers. Now if we keep increasing the circle count, at some point the layer that had 6 needs to break into 2 layers. 6 and whatever is left. Im trying to find a good solution to find this breaking point. And also might help to speed up the positioning process. – Marko Taht Jun 20 at 7:33

A greedy placement can be found as follows: Start at some point $$A_0$$ in the perimeter. Given $$A_k$$, the circle of radius $$2R$$ around $$A_k$$ will intersect the $$N$$-gon in exactly$$^1$$ two points. Let $$A_{k+1}$$ be the one in clockwise direction (for $$k\ge1$$, the other intersection will be $$A_{k-1}$$ anyway). If the distance between $$A_{k+1}$$ and $$A_0$$ is $$<2R$$, terminate: We can place $$k+1$$ circles of radius $$R$$ with centres $$A_0,A_2,\ldots, A_k$$. To estimate the maximal $$k$$ $$k$$ (or rather $$k+1$$, which is your $$K$$), we can estimate how much of the perimeter each $$A_iA_{i+1}$$ "consumes".
First assume $$2R<\frac PN$$. Then $$A_i,A_{i+1}$$ are either on the same edge of the polygon and consume exactly $$2R$$ of the perimeter length, or they consume $$a+b$$ where $$A_i$$, $$A_{i+1}$$, and a $$N$$-gon vertex $$X$$ form a triangle with side lengths $$a,b,2R$$ and $$\angle X=\pi-\frac{2\pi} N$$. It turns out that $$a+b$$ is maximized under these constraints in the symmetric case, in which $$a=b=\frac R{\cos\frac \pi N}$$. Thus from $$A_0$$ all around to $$A_{k+1}$$, we would consume at most $$P$$, but at least $$(k+1)\cdot 2R$$. We conclude $$K\cdot 2R\le P$$, or $$P-K\cdot 2R\ge 0.$$ On the other hand, if we continued the process to $$A_{k+2}$$, we would consume strictly more than $$P$$, but on the other hand at most $$(k+2)\cdot 2R+N\cdot\left(\frac{2R}{\cos\frac \pi N}-2R\right).$$ We conclude that $$(K+1)\cdot 2R+N\cdot\left(\frac{2R}{\cos\frac \pi N}-2R\right)>P.$$ You are interested in the expression on the right hand side of $$P-K\cdot 2R<2R\cdot\left(1+N\cdot\left(\frac1{\cos\frac\pi N}-1\right)\right).$$ Using $$\cos x\ge1-\frac12x^2,$$ we find \begin{align}1+N\cdot\left(\frac1{\cos\frac\pi N}-1\right)&\le1+ N\cdot\left(\frac1{1-\frac12\pi^2/N^2}-1\right)\\&=1+\frac{\frac12\pi^2/N}{1-\frac12\pi^2/N^2}\\&=1+\frac1N\cdot\frac1{\frac2{\pi^2}-\frac1N}\\&\approx 1+\frac 1N,\end{align} so in particular for large $$N$$, we cannot be much worse than $$2R$$. Heuristically, if we encounter a near-maximum situation at almost all $$N$$ vertices, we picked the wrong starting point and it seems realistic that we can cut this down to about half of the vertices. This would give us a better estimate of $$2R\cdot (1+\frac1{2N})$$, but of course still more than $$2R$$.
In order to see that "more than $$2R$$" can actually happen, just consider a situation, where $$K=N+1$$ circles snuggly fit. Then necessarily there is some loss, i.e., $$P>K\cdot (2R)$$. Now if we increase $$R$$ infinitesimally to $$R'$$, only $$K'=N$$ circles fit and we will have $$P-K'\cdot 2R'>2R'$$.
$$^1$$ unless $$R$$ is so large compared to the $$N$$-gon dimensions that we cannot expect to place more than two circles anyway
• @MarkoTaht $K$ will be between $\lceil\frac P{2R}-({\approx \frac 1N})\rceil-1$ and $\lfloor\frac P{2R} \rfloor$. Often enough, the lower and upper bound coincide – Hagen von Eitzen Jun 20 at 10:51