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

117 Views Asked by At

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

1

There are 1 best solutions below

3
On BEST ANSWER

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