3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Hagen von Eitzen Jun 20 at 7:20
  • $\begingroup$ 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. $\endgroup$ – Marko Taht Jun 20 at 7:26
  • 1
    $\begingroup$ 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.) $\endgroup$ – Blue Jun 20 at 7:28
  • $\begingroup$ @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. $\endgroup$ – Marko Taht Jun 20 at 7:33
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So if i understand this correctly K ≈ P/(2R) - 1? $\endgroup$ – Marko Taht Jun 20 at 10:28
  • $\begingroup$ @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 $\endgroup$ – Hagen von Eitzen Jun 20 at 10:51
  • $\begingroup$ I see. So if i take K = P/2R and then adjust the P to fit it all, it should work fine. $\endgroup$ – Marko Taht Jun 20 at 10:57

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.