I am trying to solve problem. I have proved that the minimum side length should be greater than or equal to radius of the circum circle of given regular polygon(by contradiction).
But I am not able to find what is the tight lower bound for it. I am curious to know if some formula can be formed for this problem or is it neccessary to use programming constructs like loops.
Please share your approaches for this.
The side length of smallest square which can embed a regular polygon with 2*n sides, where n is odd and n≥3.
geometrypolygonsprogramming
Related Solutions
Let the two known (shared) vertices be $A = (x_A , 0)$ and $B = (x_B , 0)$, and the two unknown vertices be $C = (x_C , y_C)$ and $D = (x_D , y_D)$.
Let the known variables be $x_A$ and $x_B$, and the distances $$\begin{aligned} L_{AB} &= x_B - x_A \gt 0 \\ L_{AC} &= \left\lVert\overline{A C}\right\rVert \gt 0 \\ L_{BC} &= \left\lVert\overline{B C}\right\rVert \gt 0 \\ L_{AD} &= \left\lVert\overline{A D}\right\rVert \gt 0 \\ L_{BD} &= \left\lVert\overline{B D}\right\rVert \gt 0 \\ \end{aligned}$$
Then, the system of equations that determines the location of $C$ and $D$ is $$\left\lbrace \begin{aligned} L_{AC}^2 &= (x_C - x_A)^2 + y_C^2 \\ L_{BC}^2 &= (x_C - x_B)^2 + y_C^2 \\ L_{AD}^2 &= (x_D - x_A)^2 + y_D^2 \\ L_{BD}^2 &= (x_D - x_B)^2 + y_D^2 \\ \end{aligned} \right .$$ This has four equations and four unknowns, and can be treated as two completely separate systems of equations, each with two unknowns ($x_C$ and $y_C$, and $x_D$ and $y_D$, respectively). The solution is $$\left\lbrace \begin{aligned} \displaystyle x_C &= \frac{ L_{AC}^2 - L_{BC}^2 + x_B^2 - x_A^2 }{2 ( x_B - x_A )} \\ \displaystyle y_C &= \pm \sqrt{ L_{AC}^2 - (x_C - x_A)^2 } = \pm \sqrt{ L_{BC}^2 - (x_C - x_B)^2 } \\ \displaystyle x_D &= \frac{ L_{AD}^2 - L_{BC}^2 + x_B^2 - x_A^2 }{2 ( x_B - x_A )} \\ \displaystyle y_D &= \pm \sqrt{ L_{AD}^2 - (x_D - x_A)^2 } = \pm \sqrt{ L_{BD}^2 - (x_D - x_B)^2 } \\ \end{aligned} \right.$$ If the two triangles extend to the same side, then we can choose the positive signs above (since $y_C \gt 0$ and $y_D \gt 0$). Both right sides for the two $y$ coordinates yield the same answer.
After solving $(x_C , y_C)$ and $(x_D , y_D)$ as above, their distance is obviously $$L_{CD} = \sqrt{ (x_D - x_C)^2 + (y_D - y_C)^2 }$$ Because the distance is necessarily nonnegative, you do not actually need the distance $L_{CD}$ itself; you can just compare the distance squared, $L_{CD}^2$, to the radius squared, $r_C^2$, because nonnegative values compare the same way (less, equal, greater) as their squares do. Expanding the above after squaring yields $$\begin{aligned} L_{CD}^2 &= \left( \frac{ L_{AC}^2 + L_{BD}^2 - L_{AD}^2 - L_{BC}^2 }{ 2 (x_B - x_A) } \right)^2 + \left( \sqrt{ L_{AC}^2 - (x_C - x_A)^2 } - \sqrt{ L_{AD}^2 - (x_D - x_A)^2 } \right)^2 \\ ~ &= \left( \frac{ L_{AC}^2 + L_{BD}^2 - L_{AD}^2 - L_{BC}^2 }{ 2 (x_B - x_A) } \right)^2 + \left( \sqrt{ L_{BC}^2 - (x_C - x_B)^2 } - \sqrt{ L_{BD}^2 - (x_D - x_B)^2 } \right)^2 \\ \end{aligned}$$ Both yield the same solution, to within numerical precision used.
Note that if you had just placed $A = (0, 0)$, ie. $x_A = 0$, you'd have gotten somewhat simpler solutions (and the math would have been easier, too).
For simplicity, let us consider the index $i$ of $P_i$ as the member of $\mathbb{Z}_n$.
We aim to show a stronger criterion : given points $P_1,P_2,...,P_m$ on the unit circle $\Omega$ lying in the counter-clockwise order, for each $k<m$ such that $gcd(k,m)=1$, we have $$\sum_{j=1}^m \overline{P_j P_{j+k}}\le \sum_{j=1}^m\overline{Q_j Q_{j+k}}$$ , where $Q_1,...,Q_m$ are vertices of a regular $(m)$-gon inscribed in $\Omega$.
Assuming this, we can easily show the original conjecture observing that the collection of all diagonal lines of the convex $n$-gon $P_1 P_2...P_n$ is partitioned into the cycles of the form above.
(Explicitly speaking, we can write
$$\sum_{|i-j|\ge 2}\overline{P_iP_j}=\frac{1}{2}\sum_{k=2}^{n-1}\sum_{j=1}^{gcd(k,n)}\left(\sum_{i=1}^{n/gcd(k,n)}\overline{P_{ki+j}P_{k(i+1)+j}}\right)$$ You can check this holds since each segment of LHS is counted at least twice in RHS, and the total count of segments of RHS is $(n-1)n$, which is exactly twice of the total number of terms in LHS. )
For better intuition, I post an example of $n=8$.
The collection of the diagonal segments of the octagon above is the disjoint union of the red, green, blue-colored chains plus the four main diagonals. Assuming our criterion is correct, we can argue that the total length of the segments of each color (including the main diagonals) is maximized when the polygon is regular, which concludes our proof.
Now, to show the criterion, we first exclude the trivial case $m=2$, and allow some of $P_j$'s to be the same. (but not in a switched order)
Writing $P_j=e^{i\theta_j}$, one can easily observe that the set of such $(\theta_1,...,\theta_m)\in \mathbb{T}^m$ is compact.
(Here, $\mathbb{T}^m$ is the $m$-dimensional torus $\mathbb{R}^m/\mathbb{Z}^m$ with the natural metric)
Thus, there exists a pair $(\theta_1,...,\theta_m)$ that maximizes the sum.
Now, observe that for each $j$, $P_j$ contributes only to two distinct segments : $\overline{P_jP_{j+k}}$ and $\overline{P_jP_{j-k}}$.
By the sine addition formula $\sin \alpha+\sin \beta=2\sin(\frac{\alpha+\beta}{2})\cos(\frac{\alpha-\beta}{2})$, this can be maximized only if $\overline{P_jP_{j+k}}=\overline{P_jP_{j-k}}$.
It follows that the lengths $\overline{P_jP_{j+k}}$ are all equal, which requires $P_1...P_m$ to be vertices of a regular $(m)$-gon, ending the proof of the desired criterion.
P.S. This is a formalization of the great idea suggested by Toni Mhax.
Best Answer
Let $N = 2n$ where $n \ge 3$ is odd.
Let's say we have a regular $N$-gon with circumradius $R = 1$ which fit inside a square of side $s$. Choose a coordinate system where the circumcenter is origin and the sides of square are parallel to the coordinate axes. Reflect everything upside down if needed, one can find a $\theta \in [ 0, \frac{\pi}{N} ]$ so that one of the vertex of the $N$-gon is located at $(\cos\theta,\sin\theta)$.
In terms of $\theta$, the vertices of the $N$-gon will be located at $(\cos\theta_k,\sin\theta_k)$ where $\theta_k = \theta + \frac{2\pi k}{N}$ for $k = 0,\ldots, N - 1$. In order for the $N$-gon to fit inside a square of side $s$. The shadow when we project the $N$-gon to $x$- and $y$- axes will have width $\le s$.
It is clear the width of the shadow on $x$-axis is $2\cos\theta$.
The shadow on $y$-axis is $[-\sin\theta_k,\sin\theta_k]$ for $k = \lfloor \frac{N}{4}\rfloor = \frac{n-1}{2}$. This leads to
$$s \ge 2 \max\left( \cos\theta, \sin\left(\theta + \frac{\pi(n-1)}{2n}\right)\right) = 2\max\left(\cos\theta, \cos\left(\frac{\pi}{2n}-\theta\right)\right)$$ The minimum on RHS is achieved when $\theta = \frac{\pi}{2n} - \theta \iff \theta = \frac{\pi}{4n}$. This leads to $$s \ge 2\cos\frac{\pi}{4n}$$
At $\theta =\frac{\pi}{4n}$, it is easy to see how to fit the $N$-gon into an axes-aligned square of side $2\cos\frac{\pi}{4n}$. From this, we can deduce:
As an example, for $n = 3$, we can fit a hexagon with unit circumradius into a square of $2\cos\frac{\pi}{12} \approx 1.931851652578137$