Tight bounds on the maximal perimeter and the maximal width of convex small polygons

Abstract

A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with $n=2^s$ vertices are not known when $s \ge 4$. In this paper, we construct a family of convex small n-gons, $n=2^s$ and $s\ge 3$, and show that the perimeters and the widths obtained cannot be improved for large n by more than $a/n^6$ and $b/n^4$ respectively, for certain positive constants a and b. In addition, assuming that a conjecture of Mossinghoff is true, we formulate the maximal perimeter problem as a nonlinear optimization problem involving trigonometric functions and, for $n=2^s$ with $3 \le s\le 7$, we provide global optimal solutions.

1 Introduction

The diameter of a polygon is the largest Euclidean distance between pairs of its vertices. A polygon is said to be small if its diameter equals one. For a given integer $n \ge 3$, the maximal perimeter problem consists in finding a convex small n-gon with the longest perimeter. The problem was first investigated by Reinhardt [15] in 1922, and later by Datta [9] in 1997. They proved that

• for all $n \ge 3$, the value $2n\sin \frac{\pi }{2n}$ is an upper bound on the perimeter of a convex small n-gon;

• when n is odd, the regular small n-gon is an optimal solution, but it is unique only if n is prime;

• when n is even, the regular small n-gon is not optimal;

• when n has an odd factor, there are finitely many optimal solutions [10, 11, 14] and they are all equilateral.

When n is a power of 2, the maximal perimeter problem is solved for $n \le 8$. In 1987, Tamvakis [16] found the unique convex small 4-gon with the longest perimeter, shown in Fig. 1b. Audet et al. [1] used both geometrical arguments and methods of global optimization to determine the unique convex small 8-gon with the longest perimeter, illustrated in Fig. 3c.

The diameter graph of a small polygon is the graph with the vertices of the polygon, and an edge between two vertices exists only if the distance between these vertices equals one. Figures 1, 2, and 3 represent diameter graphs of some convex small polygons. The solid lines illustrate pairs of vertices which are unit distance apart. Mossinghoff [12] conjectured that, for $n\ge 4$ power of 2, the diameter graph of a convex small n-gon with maximal perimeter has a cycle of length $n/2+1$, plus $n/2-1$ additional pendant edges, arranged so that all but two particular vertices of the cycle have a pendant edge. For example, Figs. 1b and 3c exhibit the diameter graphs of optimal n-gons when $n=4$ and when $n=8$ respectively. We point out that numerical values in figures and tables in this paper are rounded at the last reported digit.

Fig. 1

Two convex small 4-gons $(\mathtt {P}_4,L(\mathtt {P}_4)),W(\mathtt {P}_4))$

Fig. 2

Three convex small 6-gons $(\mathtt {P}_6,L(\mathtt {P}_6)),W(\mathtt {P}_6))$

Fig. 3

Four convex small 8-gons $(\mathtt {P}_8,L(\mathtt {P}_8)),W(\mathtt {P}_8))$

The width of a polygon in some direction is the distance between two parallel lines perpendicular to this direction and supporting the polygon from below and above. The width of a polygon is the minimum width for all directions. For a given integer $n \ge 3$, the maximal width problem consists in finding a convex small n-gon with the largest width. This problem was partially solved by Bezdek and Fodor [6] in 2000. They proved that

• for all $n \ge 3$, the value $\cos \frac{\pi }{2n}$ is an upper bound on the width of a convex small n-gon;

• when n has an odd factor, a convex small n-gon is optimal for the maximal width problem if and only if it is optimal for the maximal perimeter problem;

• when $n = 4$, there are infinitely many optimal convex small 4-gons, including the 4-gon illustrated in Fig. 1b.

When $n\ge 8$ is a power of 2, the maximal width is only known for the first open case $n = 8$. Audet et al. [4] combined geometrical and analytical reasoning as well as methods of global optimization to prove that there are infinitely many optimal convex small 8-gons, including the 8-gon illustrated in Fig. 3d.

For $n=2^s$ with integer $s\ge 4$, exact solutions in both problems appear to be presently out of reach. However, tight lower bounds on the maximal perimeter and the maximal width may be obtained analytically. For instance, Mossinghoff [12] constructed convex small n-gons, for $n=2^s$ with $s\ge 3$, and proved that the perimeters obtained cannot be improved for large n by more than $\pi ^5/(16n^5)$. We can also show that, when $n=2^s$ with $s\ge 2$, the value $\cos \frac{\pi }{2n-2}$ is a lower bound on the maximal width and this bound cannot be improved for large n by more than $\pi ^2/(4n^3)$. In this paper, we propose tighter lower bounds on both the maximal perimeter and the maximal width of convex small n-gons when $n=2^s$ and integer $s \ge 3$. Thus, the main result of this paper is the following:

Theorem 1

For a given integer $n \ge 3$, let $\overline{L}_n := 2n \sin \frac{\pi }{2n}$ denote an upper bound on the perimeter $L(\mathtt {P}_n)$ of a convex small n-gon $\mathtt {P}_n$, and $\overline{W}_n := \cos \frac{\pi }{2n}$ denote an upper bound on its width $W(\mathtt {P}_n)$. If $n = 2^s$ with $s\ge 3$, then there exists a convex small n-gon $\mathtt {B}_n$ such that

$$\begin{aligned} L(\mathtt {B}_n)&= 2n \sin \frac{\pi }{2n} \cos \left( \frac{\pi }{2n}-\frac{1}{2}\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n}\right) \right) ,\\ W(\mathtt {B}_n)&= \cos \left( \frac{\pi }{n} - \frac{1}{2}\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n}\right) \right) , \end{aligned}$$

and

$$\begin{aligned} \overline{L}_n - L(\mathtt {B}_n)&= \frac{\pi ^7}{32n^6} + O\left( \frac{1}{n^8}\right) ,\\ \overline{W}_n - W(\mathtt {B}_n)&= \frac{\pi ^4}{8n^4} + O\left( \frac{1}{n^6}\right) . \end{aligned}$$

The remainder of this paper is organized as follows. Section 2 recalls principal results on the maximal perimeter and the maximal width of convex small polygons. We prove Theorem 1 in Sect. 3. Tight bounds on the maximal width of unit-perimeter n-gons, $n=2^s$ and $s\ge 3$, are deduced from Theorem 1 in Sect. 4. Under the assumption that Mossinghoff’s conjecture is true, a nonlinear optimization problem involving trigonometric functions is proposed for the maximal perimeter problem in Sect. 5. Global optimal solutions obtained by using AMPL with the solver Couenne [5] are given for $n= 2^s$ with $3\le s \le 7$. Section 6 concludes the paper.

2 Perimeters and widths of convex small polygons

2.1 Maximal perimeter and maximal width

Let $L(\mathtt {P})$ denote the perimeter of a polygon $\mathtt {P}$ and $W(\mathtt {P})$ its width. For a given integer $n\ge 3$, let $\mathtt {R}_n$ denote the regular small n-gon. We have

$$\begin{aligned} L(\mathtt {R}_n) = {\left\{ \begin{array}{ll} 2n\sin \frac{\pi }{2n} &{}\text {if}\; n\; \text {is odd,}\\ n\sin \frac{\pi }{n} &{}\text {if}\; n\; \text {is even,}\\ \end{array}\right. } \end{aligned}$$

and

$$\begin{aligned} W(\mathtt {R}_n) = {\left\{ \begin{array}{ll} \cos \frac{\pi }{2n} &{}\text {if}\; n\; \text {is odd,}\\ \cos \frac{\pi }{n} &{}\text {if}\; n\; \text {is even.}\\ \end{array}\right. } \end{aligned}$$

We remark that $L(\mathtt {R}_n) < L(\mathtt {R}_{n-1})$ [3] and $W(\mathtt {R}_n) < W(\mathtt {R}_{n-1})$ for all even $n\ge 4$. The polygon $\mathtt {R}_n$ does not have maximum perimeter nor maximum width for any even $n\ge 4$. Indeed, when n is even, one can construct a convex small n-gon with a longer perimeter and a larger width than $\mathtt {R}_n$ by adding a vertex at distance 1 along the mediatrix of an angle in $\mathtt {R}_{n-1}$. We denote this n-gon by $\mathtt {R}_{n-1}^+$ and we have

$$\begin{aligned} L(\mathtt {R}_{n-1}^+)&= (2n-2)\sin \frac{\pi }{2n-2} + 4 \sin \frac{\pi }{4n-4} - 2\sin \frac{\pi }{2n-2},\\ W(\mathtt {R}_{n-1}^+)&= \cos \frac{\pi }{2n-2}. \end{aligned}$$

When n has an odd factor m, we construct another family of convex equilateral small n-gons as follows:

• 1. Consider a regular small m-gon $\mathtt {R}_m$;

• 2. Transform $\mathtt {R}_m$ into a Reuleaux m-gon by replacing each edge by a circle’s arc passing through its end vertices and centered at the opposite vertex;

• 3. Add at regular intervals $n/m-1$ vertices within each arc;

• 4. Take the convex hull of all vertices.

We denote these n-gons by $\mathtt {R}_{m,n}$ and we have

$$\begin{aligned} L(\mathtt {R}_{m,n})&= 2n\sin \frac{\pi }{2n},\\ W(\mathtt {R}_{m,n})&= \cos \frac{\pi }{2n}. \end{aligned}$$

The 6-gon $\mathtt {R}_{3,6}$ is illustrated in Fig. 2c.

Theorem 2

(Reinhardt [15], Datta [9]) For all $n \ge 3$, let $L_n^*$ denote the maximal perimeter among all convex small n-gons and let $\overline{L}_n := 2n \sin \frac{\pi }{2n}$.

• When n has an odd factor m, $L_n^* = \overline{L}_n$ is achieved by finitely many equilateral n-gons [10, 11, 14], including $\mathtt {R}_{m,n}$. The optimal n-gon $\mathtt {R}_{m,n}$ is unique if m is prime and $n/m \le 2$.

• When $n=2^s$ with integer $s\ge 2$, $L(\mathtt {R}_n)< L_n^* < \overline{L}_n$.

When $n=2^s$, the maximal perimeter $L_n^*$ is only known for $s \le 3$. Tamvakis [16] found that $L_4^* = 2+\sqrt{6}-\sqrt{2}$, and this value is achieved only by $\mathtt {R}_3^+$, shown in Fig. 1b. Audet et al. [1] found that $L_8^* \approx 3.121147$, and this value is only achieved by $\mathtt {B}_8^*$, shown in Fig. 3c.

Theorem 3

(Bezdek and Fodor [6]) For all $n \ge 3$, let $W_n^*$ denote the maximal width among all convex small n-gons and let $\overline{W}_n := \cos \frac{\pi }{2n}$.

• When n has an odd factor, $W_n^* = \overline{W}_n$ is achieved by a convex small n-gon with maximal perimeter $L_n^* = \overline{L}_n$.

• When $n=2^s$ with integer $s\ge 2$, $W(\mathtt {R}_n)< W_n^* < \overline{W}_n$.

When $n = 2^s$, the maximal width $W_n^*$ is only known for $s \le 3$. Bezdek and Fodor [6] showed that $W_4^* = \frac{1}{2}\sqrt{3}$, and this value is achieved by infinitely many convex small 4-gons, including $\mathtt {R}_3^+$ shown in Fig. 1b. Audet, Hansen, Messine, and Ninin found that $W_8^* = \frac{1}{4}\sqrt{10+2\sqrt{7}}$, and this value is also achieved by infinitely many convex small 8-gons, including $\mathtt {B}_8$ shown in Fig. 3d. It is interesting to note that while the optimal 4-gon for the maximal perimeter problem is also optimal for the maximal width problem, the optimal 8-gon for the maximal perimeter problem is not optimal for the maximal width problem.

2.2 Lower bounds on the maximal perimeter and the maximal width

For $n=2^s$ with integer $s\ge 2$, let $\mathtt {T}_n$ denote the convex n-gon obtained by subdividing each bounding arc of a such Reuleaux triangle into either $\lceil n/3 \rceil$ or $\lfloor n/3 \rfloor$ subarcs of equal length, then taking the convex hull of the endpoints of these arcs. For a real number a, $\lceil a \rceil$ is the least integer greater than or equal to a, and $\lfloor a \rfloor$ is the greatest integer less than or equal to a. We illustrate $\mathtt {T}_n$ for some n in Fig. 4. For each n, the perimeter of $\mathtt {T}_n$ is given by

$$\begin{aligned} L(\mathtt {T}_n) = {\left\{ \begin{array}{ll} \frac{4n-4}{3}\sin \frac{\pi }{2n-2} + \frac{2n+4}{3}\sin \frac{\pi }{2n+4} &{}\text {if}\; n = 3k+1,\\ \frac{4n+4}{3}\sin \frac{\pi }{2n+2} + \frac{2n-4}{3}\sin \frac{\pi }{2n-4} &{}\text {if}\; n = 3k+2.\\ \end{array}\right. } \end{aligned}$$

Fig. 4

Tamvakis polygons $(\mathtt {T}_n,L(\mathtt {T}_n),W(\mathtt {T}_n))$

We note that $\mathtt {T}_4$ is optimal for the maximal perimeter problem and we can show that

$$\begin{aligned} \overline{L}_n - L(\mathtt {T}_n) = \frac{\pi ^3}{4n^4} + O \left( \frac{1}{n^5}\right) \end{aligned}$$

for all $n=2^s$ and $s\ge 2$. By contrast,

$$\begin{aligned} \overline{L}_n - L(\mathtt {R}_n)&= \frac{\pi ^3}{8n^2} + O \left( \frac{1}{n^4}\right) ,\\ \overline{L}_n - L(\mathtt {R}_{n-1}^+)&= \frac{5\pi ^3}{96n^3} + O \left( \frac{1}{n^4}\right) \end{aligned}$$

for all even $n\ge 4$. Tamvakis asked if $\mathtt {T}_n$ is also optimal when $s \ge 3$. Obviously, $\mathtt {T}_8$ is not optimal, i.e., $L(\mathtt {T}_8) < L_8^*$.

For all $n = 2^s$ with integer $s\ge 2$, let $\mathtt {P}_n^*$ denote a convex small n-gon with the longest perimeter.

Conjecture 1

(Mossinghoff [12]) For all $n = 2^s$ with integer $s\ge 2$, the diameter graph of $\mathtt {P}_n^*$ has a cycle of length $n/2+1$, plus $n/2-1$ additional pendant edges, arranged so that all but two particular vertices of the cycle have a pendant edge.

Conjecture 2

(Mossinghoff [12]) For all $n = 2^s$ with integer $s\ge 2$, $\mathtt {P}_n^*$ has an axis of symmetry corresponding to one particular pendant edge in its diameter graph.

Conjecture 1 is proven for $n=4$ [16] and $n=8$ [1]. Conjecture 2 is only proven for $n=4$ [16], but it is shown numerically for $n=8$ in [1]. Mossinghoff [12] constructed a family of convex small n-gons $\mathtt {M}_n$ having the diameter graph described in Conjectures 1 and 2 . These polygons have the property that

$$\begin{aligned} \overline{L}_n - L(\mathtt {M}_n) = \frac{\pi ^5}{16n^5} + O \left( \frac{1}{n^6}\right) \end{aligned}$$

when $n=2^s$ and $s\ge 3$. We show $\mathtt {M}_n$ for some n in Fig. 5.

Fig. 5

Mossinghoff polygons $(\mathtt {M}_n,L(\mathtt {M}_n),W(\mathtt {M}_n))$

On the other hand, for all $n=2^s$ and integer $s\ge 3$,

$$\begin{aligned} W(\mathtt {T}_n)&= {\left\{ \begin{array}{ll} \cos \frac{\pi }{2n-2} &{}\text {if}\; n = 3k+1,\\ \cos \frac{\pi }{2n-4} &{}\text {if}\; n = 3k+2, \end{array}\right. }\\ W(\mathtt {M}_n)&= \cos \left( \frac{\pi }{2n}+\frac{\pi ^2}{4n^2} - \frac{\pi ^2}{2n^3}\right) , \end{aligned}$$

and we can show that $W(\mathtt {R}_{n-1}^+)\ge \max \{W(\mathtt {T}_n), W(\mathtt {M}_n)\}$. Note that

$$\begin{aligned} \overline{W}_n - W(\mathtt {R}_n)&= \frac{3\pi ^2}{8n^2} + O\left( \frac{1}{n^4}\right) ,\\ \overline{W}_n - W(\mathtt {R}_{n-1}^+)&= \frac{\pi ^2}{4n^3} + O\left( \frac{1}{n^4}\right) \end{aligned}$$

for all even $n\ge 4$.

3 Proof of Theorem 1

We use cartesian coordinates to describe an n-gon $\mathtt {P}_n$, assuming that a vertex $\mathtt {v}_i$, $i=0,1,\ldots ,n-1$, is positioned at abscissa $x_i$ and ordinate $y_i$. Placing the vertex $\mathtt {v}_0$ at the origin, we set $x_0 = y_0 = 0$. We also assume that the n-gon $\mathtt {P}_n$ is in the half-plane $y\ge 0$.

For all $n=2^s$ with integer $s\ge 3$, consider the n-gon $\mathtt {P}_n$ having an $(n/2+1)$-length cycle: $\mathtt {v}_{0}-\mathtt {v}_1-\cdots -\mathtt {v}_k-\cdots -\mathtt {v}_{\frac{n}{4}} - \mathtt {v}_{\frac{n}{4}+1} - \cdots - \mathtt {v}_{\frac{n}{2}-k+1}-\cdots -\mathtt {v}_{\frac{n}{2}}-\mathtt {v}_0$ plus $n/2-1$ pendant edges: $\mathtt {v}_{0} - \mathtt {v}_{\frac{n}{2}+1}$, $\mathtt {v}_k - \mathtt {v}_{k + \frac{n}{2} + 1}$, $\mathtt {v}_{\frac{n}{2}-k+1} - \mathtt {v}_{n-k}$, $k = 1,\ldots , n/4-1$, as illustrated in Fig. 6. We assume that $\mathtt {P}_n$ has the edge $\mathtt {v}_{0}-\mathtt {v}_{\frac{n}{2}+1}$ as axis of symmetry and for all $k=1,\ldots , n/4-1$, the pendant edge $\mathtt {v}_k - \mathtt {v}_{k + \frac{n}{2} + 1}$ bisects the angle $\angle \mathtt {v}_{k-1} \mathtt {v}_k \mathtt {v}_{k+1}$.

Fig. 6

Definition of variables $\alpha _0, \alpha _1, \ldots , \alpha _{\frac{n}{4}}$ for $\mathtt {B}_n$: Case of $n=8$ vertices

Let $\alpha _0 := \angle \mathtt {v}_{\frac{n}{2}+1} \mathtt {v}_{0} \mathtt {v}_1$, $2\alpha _k := \angle \mathtt {v}_{k-1} \mathtt {v}_{k} \mathtt {v}_{k+1}$ for all $k=1,\ldots , n/4-1$, and $\alpha _{\frac{n}{4}} := \angle \mathtt {v}_{\frac{n}{4}-1} \mathtt {v}_{\frac{n}{4}} \mathtt {v}_{\frac{n}{4}+1}$. Since $\mathtt {P}_n$ is symmetric, we have

$$\begin{aligned} \alpha _0 + 2\sum _{k=1}^{n/4-1}\alpha _k + \alpha _{n/4} = \frac{\pi }{2}, \end{aligned}$$

(1)

and

$$\begin{aligned} L(\mathtt {P}_n)&= 4\sin \frac{\alpha _0}{2} + 8 \sum _{k=1}^{n/4-1} \sin \frac{\alpha _k}{2} + 4\sin \frac{\alpha _{n/4}}{2}, \end{aligned}$$

(2a)

$$\begin{aligned} W(\mathtt {P}_n)&= \min _{k=0,1,\ldots ,n/4} \cos \frac{\alpha _k}{2}. \end{aligned}$$

(2b)

By placing the vertex $\mathtt {v}_{0}$ at (0, 0) in the plane, and the vertex $\mathtt {v}_{\frac{n}{2}+1}$ at (0, 1), we have

$$\begin{aligned} x_1&= \sin \alpha _0 = -x_{n/2}, \end{aligned}$$

(3a)

$$\begin{aligned} y_1&= \cos \alpha _0 = y_{n/2},\end{aligned}$$

(3b)

$$\begin{aligned} x_k&= x_{k-1} - (-1)^k \sin \left( \alpha _0 + 2\sum _{j=1}^{k-1}\alpha _j\right) = - x_{\frac{n}{2} - k + 1} \quad \forall k=2,3,\ldots ,n/4\end{aligned}$$

(3c)

$$\begin{aligned} y_k&= y_{k-1} - (-1)^k \cos \left( \alpha _0 + 2\sum _{j=1}^{k-1}\alpha _j\right) = y_{\frac{n}{2} - k + 1} \quad \forall k=2,3,\ldots ,n/4,\end{aligned}$$

(3d)

$$\begin{aligned} x_{k+\frac{n}{2}+1}&= x_{k} + (-1)^k \sin \left( \alpha _0 + 2\sum _{j=1}^{k-1}\alpha _j + \alpha _k \right) = - x_{n-k} \quad \forall k=1,2,\ldots ,n/4-1,\end{aligned}$$

(3e)

$$\begin{aligned} y_{k+\frac{n}{2}+1}&= y_{k} + (-1)^k \cos \left( \alpha _0 + 2\sum _{j=1}^{k-1}\alpha _j + \alpha _k \right) = y_{n-k} \quad \forall k=1,2,\ldots ,n/4-1. \end{aligned}$$

(3f)

We also have

$$\begin{aligned} x_{\frac{n}{4}} = -1/2 = -x_{\frac{n}{4}+1}. \end{aligned}$$

(4)

since the edge $\mathtt {v}_{\frac{n}{4}} - \mathtt {v}_{\frac{n}{4}+1}$ is horizontal and $\Vert \mathtt {v}_{\frac{n}{4}} - \mathtt {v}_{\frac{n}{4}+1}\Vert = 1$.

For all $k=0,1,\ldots ,n/4$, suppose $\alpha _k = \frac{\pi }{n} + (-1)^k \beta$ with $\beta = \beta (n)$ satisfying $|\beta | < \frac{\pi }{n}$. Then (1) is verified and (2) becomes

$$\begin{aligned} L(\mathtt {P}_n)&= n\sin \left( \frac{\pi }{2n}+\frac{\beta }{2}\right) + n\sin \left( \frac{\pi }{2n}-\frac{\beta }{2}\right) = 2n \sin \frac{\pi }{2n}\cos \frac{\beta }{2},\end{aligned}$$

(5a)

$$\begin{aligned} W(\mathtt {P}_n)&= \cos \left( \frac{\pi }{2n} + \frac{|\beta |}{2}\right) . \end{aligned}$$

(5b)

Coordinates $(x_i,y_i)$ in (3) are given by

$$\begin{aligned} x_{k}&= \sum _{j=1}^k (-1)^{j-1} \sin \left( (2j-1)\frac{\pi }{n}+(-1)^{j-1}\beta \right) \nonumber \\&= \frac{\sin \frac{2k\pi }{n} \sin \left( \beta - (-1)^k\frac{\pi }{n}\right) }{\sin \frac{2\pi }{n}} = - x_{\frac{n}{2}-k+1} \quad \forall k=1,2,\ldots ,n/4, \end{aligned}$$

(6a)

$$\begin{aligned} y_{k}&= \sum _{j=1}^k (-1)^{j-1} \cos \left( (2j-1)\frac{\pi }{n}+(-1)^{j-1}\beta \right) \nonumber \\&= \frac{\sin \left( \frac{\pi }{n}-\beta \right) +\cos \frac{2k\pi }{n}\sin \left( \beta - (-1)^k\frac{\pi }{n}\right) }{\sin \frac{2\pi }{n}} = y_{\frac{n}{2}-k+1} \quad \forall k=1,2,\ldots ,n/4,\end{aligned}$$

(6b)

$$\begin{aligned} x_{k+\frac{n}{2}+1}&= x_{k} + (-1)^k \sin \frac{2k\pi }{n} = - x_{n-k} \quad \forall k=1,2,\ldots ,n/4-1,\end{aligned}$$

(6c)

$$\begin{aligned} y_{k+\frac{n}{2}+1}&= y_{k} + (-1)^k \cos \frac{2k\pi }{n} = y_{n-k} \quad \forall k=1,2,\ldots ,n/4-1. \end{aligned}$$

(6d)

Finally, $\beta$ is chosen so that (4) is satisfied. It follows, from (6a),

$$\begin{aligned} \frac{\sin \left( \beta -\frac{\pi }{n}\right) }{\sin \frac{2\pi }{n}} = -\frac{1}{2} \Rightarrow \beta = \beta _0(n) = \frac{\pi }{n}-\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n}\right) = \frac{\pi ^3}{2n^3} + \frac{\pi ^5}{8n^5} + O\left( \frac{1}{n^7}\right) . \end{aligned}$$

Let $\mathtt {B}_n$ denote the n-gon obtained by setting $\beta = \beta _0(n)$. From (5), we have

$$\begin{aligned} L(\mathtt {B}_n)&= 2n \sin \frac{\pi }{2n} \cos \left( \frac{\pi }{2n}-\frac{1}{2}\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n}\right) \right) ,\\ W(\mathtt {B}_n)&= \cos \left( \frac{\pi }{n}-\frac{1}{2}\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n} \right) \right) , \end{aligned}$$

and

$$\begin{aligned} \overline{L}_n - L(\mathtt {B}_n)&= \frac{\pi ^7}{32n^6} + \frac{11\pi ^9}{768n^8} + O\left( \frac{1}{n^{10}}\right) ,\\ \overline{W}_n - W(\mathtt {B}_n)&= \frac{\pi ^4}{8n^4} + \frac{11\pi ^6}{192n^6} + O\left( \frac{1}{n^{8}}\right) . \end{aligned}$$

By construction, $\mathtt {B}_n$ is small and convex for all $n=2^s$ and $s \ge 3$. We illustrate $\mathtt {B}_n$ for some n in Fig. 7. This completes the proof of Theorem 1. $\square$

Fig. 7

Polygons $(\mathtt {B}_n,L(\mathtt {B}_n),W(\mathtt {B}_n))$ defined in Theorem 1

We implemented all polygons presented in this work as a MATLAB package: OPTIGON, freely available on GitHub [8]. In OPTIGON, MATLAB functions that give the coordinates of the vertices are provided. An algorithm developed in [7] to estimate the maximal area of a small n-gon [15] when $n \ge 6$ is even can be also found.

Table 1 shows the perimeters of $\mathtt {B}_n$, along with the upper bounds $\overline{L}_n$, the perimeters of $\mathtt {R}_n$, $\mathtt {R}_{n-1}^+$, $\mathtt {T}_n$, and $\mathtt {M}_n$ for $n=2^s$ and $3 \le s \le 7$. As suggested by Theorem 1, when n is a power of 2, $\mathtt {B}_n$ provides a tighter lower bound on the maximal perimeter $L_n^*$ compared to the best prior convex small n-gon $\mathtt {M}_n$. For instance, we can note that $L_{128}^* - L(\mathtt {B}_{128})< \overline{L}_{128} - L(\mathtt {B}_{128}) < 2.15 \times 10^{-11}$. By analysing the fraction $\frac{L(\mathtt {B}_n) - L(\mathtt {M}_n)}{\overline{L}_n - L(\mathtt {M}_n)}$ of the length of the interval $[L(\mathtt {M}_n), \overline{L}_n]$ where $L(\mathtt {B}_n)$ lies, it is not surprising that $L(\mathtt {B}_n)$ approaches $\overline{L}_n$ much faster than $L(\mathtt {M}_n)$ does as n increases. After all, $L(\mathtt {B}_n) - L(\mathtt {M}_n) \sim \frac{\pi ^5}{16n^5}$ for large n.

Table 1 Perimeters of $\mathtt {B}_n$

Table 2 displays the widths of $\mathtt {B}_n$, along with the upper bounds $\overline{W}_n$, the widths of $\mathtt {R}_n$ and $\mathtt {R}_{n-1}^+$. Again, when $n=2^s$, $\mathtt {B}_n$ provides a tighter lower bound for the maximal width $W_n^*$ compared to the best prior convex small n-gon $\mathtt {R}_{n-1}^+$. We also remark that $W(\mathtt {B}_n)$ approaches $\overline{W}_n$ much faster than $W(\mathtt {R}_{n-1}^+)$ does as n increases. It is interesting to note that $W(\mathtt {B}_8) = W_8^*$, i.e., $\mathtt {B}_8$ is an optimal solution for the maximal width problem when $n=8$.

Table 2 Widths of $\mathtt {B}_n$

Propositions 1 and 2 highlight some interesting properties of $\mathtt {B}_n$.

Proposition 1

Let $n=2^s$ with integer $s\ge 3$.

• 1. The coordinates of the vertex $\mathtt {v}_{\frac{n}{4}}$ in $\mathtt {B}_n$ are $(-1/2,1/2)$.

• 2. For all $k=1,\ldots ,n/4-1$, the pendant edge $\mathtt {v}_{k} - \mathtt {v}_{k+\frac{n}{2}+1}$ of $\mathtt {B}_n$ passes through the point $\mathtt {u}=(0,1/2)$.

Proof

Let $n=2^s$ with integer $s\ge 3$ and $\beta = \frac{\pi }{n}-\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n}\right)$.

• 1. We have, from (6a),

  $$\begin{aligned} x_{\frac{n}{4}}&= \frac{\sin \left( \beta - \frac{\pi }{n}\right) }{\sin \frac{2\pi }{n}} = -\frac{1}{2},\\ y_{\frac{n}{4}}&= \frac{\sin \left( \frac{\pi }{n} - \beta \right) }{\sin \frac{2\pi }{n}} = \frac{1}{2}. \end{aligned}$$

• 2. For all $k=1,\ldots ,n/4-1$, coordinates $(x_i,y_i)$ in (6) are

  $$\begin{aligned} x_{k}&= \frac{\sin \frac{2k\pi }{n} \sin \left( \beta - (-1)^k\frac{\pi }{n}\right) }{\sin \frac{2\pi }{n}},&x_{k+\frac{n}{2}+1}&= x_{k} + (-1)^k \sin \frac{2k\pi }{n},\\ y_{k}&= \frac{1}{2} + \frac{\cos \frac{2k\pi }{n}\sin \left( \beta - (-1)^k\frac{\pi }{n}\right) }{\sin \frac{2\pi }{n}},&y_{k+\frac{n}{2}+1}&= y_{k} + (-1)^k \cos \frac{2k\pi }{n}. \end{aligned}$$

  It follows that, for all $k=1,\ldots ,n/4-1$,

  $$\begin{aligned} \frac{x_{k+\frac{n}{2}+1} - x_{k}}{y_{k+\frac{n}{2}+1} - y_{k}} = \tan \frac{2k\pi }{n} = \frac{x_{k}}{y_{k} - \frac{1}{2}}, \end{aligned}$$

  i.e., the pendant edge $\mathtt {v}_{k} - \mathtt {v}_{k+\frac{n}{2}+1}$ passes through the point $\mathtt {u}=(0,1/2)$. $\square$

Proposition 2

Let $n=2^s$ with integer $s\ge 3$. The area of $\mathtt {B}_n$ is $\frac{n}{8} \sin \frac{2\pi }{n}$, which is the area of the regular small n-gon $\mathtt {R}_n$.

Proof

Let $n=2^s$ with integer $s\ge 3$ and $\beta = \frac{\pi }{n}-\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n}\right)$. Let $A_0$ be the area of the quadrilateral $\mathtt {u} \mathtt {v}_{1} \mathtt {v}_{\frac{n}{2}+1} \mathtt {v}_{\frac{n}{2}}$, $A_k$ be the area of the quadrilateral $\mathtt {u} \mathtt {v}_{k+1} \mathtt {v}_{k+\frac{n}{2}+1} \mathtt {v}_{k-1}$ for all $k=1,\ldots ,n/4-1$, and $A_{\frac{n}{4}}$ be the area of the triangle $\mathtt {u} \mathtt {v}_{\frac{n}{4}+1} \mathtt {v}_{\frac{n}{4}-1}$, where $\mathtt {u}=(0,1/2)$. The area of $\mathtt {B}_n$ is given by

$$\begin{aligned} A(\mathtt {B}_n) = A_0 + 2\sum _{k=1}^{n/4-1}A_k + 2A_{\frac{n}{4}}. \end{aligned}$$

We have

$$\begin{aligned} A_0&= \frac{1}{2}\Vert \mathtt {v}_{\frac{n}{2}+1}-\mathtt {u}\Vert \Vert \mathtt {v}_{\frac{n}{2}} - \mathtt {v}_{1}\Vert = \frac{1}{2}\sin \left( \frac{\pi }{n}+\beta \right) ,\\ A_k&= \frac{1}{2}\Vert \mathtt {v}_{k+\frac{n}{2}+1}-\mathtt {u}\Vert \Vert \mathtt {v}_{k-1} - \mathtt {v}_{k+1}\Vert \\&= {\left\{ \begin{array}{ll} \frac{1}{2}\sin \left( \frac{\pi }{n}+\beta \right) &{}\text {if}\; k\; \text {is even},\\ \frac{1}{2}\sin \frac{2\pi }{n} - \frac{1}{2}\sin \left( \frac{\pi }{n}+\beta \right) &{}\text {if}\; k\; \text {is odd}, \end{array}\right. } \end{aligned}$$

for all $k=1,\ldots ,n/4-1$, and

$$\begin{aligned} A_{\frac{n}{4}} = \frac{1}{2}(x_{\frac{n}{4}+1}(y_{\frac{n}{4}-1}-1/2) - (y_{\frac{n}{4}+1}-1/2) x_{\frac{n}{4}-1}) = \frac{1}{4} \sin \left( \frac{\pi }{n}+\beta \right) . \end{aligned}$$

Thus,

$$\begin{aligned} A(\mathtt {B}_n) = \frac{n}{8}\sin \left( \frac{\pi }{n}+\beta \right) + \frac{n}{8}\left( \sin \frac{2\pi }{n} - \sin \left( \frac{\pi }{n}+\beta \right) \right) = \frac{n}{8}\sin \frac{2\pi }{n}. \end{aligned}$$

$\square$

4 Tight bounds on the maximal width of unit-perimeter polygons

Let $\hat{\mathtt {P}}$ denote the polygon obtained by contracting a small polygon $\mathtt {P}$ so that $L(\hat{\mathtt {P}}) = 1$. Thus, the width of the unit-perimeter polygon $\hat{\mathtt {P}}$ is given by $W(\hat{\mathtt {P}}) = W(\mathtt {P})/L(\mathtt {P})$. For a given integer $n\ge 3$,

$$\begin{aligned} W(\hat{\mathtt {R}}_n) = {\left\{ \begin{array}{ll} \frac{1}{2n} \cot \frac{\pi }{2n} &{}\text {if}\; n\; \text {is odd,}\\ \frac{1}{n} \cot \frac{\pi }{n} &{}\text {if}\; n\; \text {is even.}\\ \end{array}\right. } \end{aligned}$$

We remark that $W(\hat{\mathtt {R}}_n) < W(\hat{\mathtt {R}}_{n-1})$ for all even $n\ge 4$. The polygon $\hat{\mathtt {R}}_n$ does not have maximum width for any even $n\ge 4$. When n is even, one can construct a unit-perimeter n-gon with the same width as $\hat{\mathtt {R}}_{n-1}$ by adding a vertex in the middle of a side of $\hat{\mathtt {R}}_{n-1}$.

When n has an odd factor m, one can note that

$$\begin{aligned} W(\hat{\mathtt {R}}_{m,n}) = \frac{1}{2n} \cot \frac{\pi }{2n}. \end{aligned}$$

Theorem 4

(Audet et al. [2]) For all $n \ge 3$, let $w_n^*$ denote the maximal width among all unit-perimeter n-gons and let $\overline{w}_n := \frac{1}{2n} \cot \frac{\pi }{2n}$.

• When n has an odd factor m, $w_n^* = \overline{w}_n$ is achieved by finitely many equilateral n-gons [10, 11, 14], including $\mathtt {R}_{m,n}$. The optimal n-gon $\hat{\mathtt {R}}_{m,n}$ is unique if m is prime and $n/m \le 2$.

• When $n=2^s$ with integer $s\ge 2$, $W(\hat{\mathtt {R}}_n)< \overline{w}_{n-1} \le w_n^* < \overline{w}_n$.

When $n=2^s$, the maximal width $w_n^*$ of unit-perimeter n-gons is only known for $s=2$. Audet et al. [2] showed that $w_4^* = \frac{1}{4}\sqrt{6\sqrt{3}-9} > \overline{w}_3 = \frac{1}{6}\sqrt{3}$. For $s\ge 3$, exact solutions appear to be presently out of reach. However, it is interesting to note that

$$\begin{aligned} W(\hat{\mathtt {B}}_n) = \frac{1}{2n}\left( \cot \frac{\pi }{2n} - \tan \left( \frac{\pi }{2n}-\frac{1}{2}\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n}\right) \right) \right) \end{aligned}$$

is a tighter lower bound compared to $\overline{w}_{n-1}$ on $w_n^*$ when $n=2^s$ and $s\ge 3$. Indeed, we can show that, for all $n=2^s$ and integer $s\ge 3$,

$$\begin{aligned} \overline{w}_n - W(\hat{\mathtt {B}}_n) = \frac{1}{2n}\tan \left( \frac{\pi }{2n}-\frac{1}{2}\arcsin \left( \frac{1}{2}\sin \frac{2\pi }{n}\right) \right) = \frac{\pi ^3}{8n^4} + O\left( \frac{1}{n^6}\right) , \end{aligned}$$

while

$$\begin{aligned} \overline{w}_n - W(\hat{\mathtt {R}}_n)&= \frac{\pi }{4n^2} + O\left( \frac{1}{n^4}\right) ,\\ \overline{w}_n - \overline{w}_{n-1}&= \frac{\pi }{6n^3} + O\left( \frac{1}{n^4}\right) \end{aligned}$$

for all even $n\ge 4$.

Table 3 lists the widths of $\hat{\mathtt {B}}_n$, along with the upper bounds $\overline{w}_n$, the lower bounds $\overline{w}_{n-1}$, and the widths of $\hat{\mathtt {R}}_n$ for $n=2^s$ and $3\le s \le 7$. As n increases, it is not surprising that $W(\hat{\mathtt {B}}_n)$ approaches $\overline{W}_n$ much faster than $\overline{w}_{n-1}$ does.

Table 3 Widths of $\hat{\mathtt {B}}_n$

5 Solving the maximal perimeter problem

For any $n=2^s$ with integer $s\ge 3$, we can construct a convex small n-gon $\mathtt {B}_n^*$ with a longer perimeter than $\mathtt {B}_n$ by adjusting the angles $\alpha _0, \alpha _1, \ldots , \alpha _{\frac{n}{4}}$ from the parametrization of Sect. 3 to maximize the perimeter $L(\mathtt {P}_n)$ in (2a) [12]. Hence, $L(\mathtt {B}_n^*)$ is the optimal value of the problem:

$$\begin{aligned}&L(\mathtt {B}_n^*) = \max _{\varvec{\alpha }} \quad L(\mathtt {P}_n) = 4\sin \frac{\alpha _0}{2} + \sum _{k=1}^{n/4-1} 8\sin \frac{\alpha _k}{2} + 4\sin \frac{\alpha _{n/4}}{2} \end{aligned}$$

(7a)

$$\begin{aligned}&{{\,\mathrm{s.t.}\,}}\quad \alpha _0 + \sum _{k=1}^{n/4-1} 2\alpha _k + \alpha _{n/4} = \pi /2,\end{aligned}$$

(7b)

$$\begin{aligned}&\sin \alpha _0 - \sum _{k=2}^{n/4} (-1)^k \sin \left( \alpha _0 + \sum _{i=1}^{k-1} 2\alpha _i\right) = -1/2,\end{aligned}$$

(7c)

$$\begin{aligned}&0 \le \alpha _k \le \pi /6 \quad \forall k = 0,1, \ldots , n/4-1,\end{aligned}$$

(7d)

$$\begin{aligned}&0 \le \alpha _{n/4} \le \pi /3,\end{aligned}$$

(7e)

$$\begin{aligned}&L(\mathtt {P}_n) \ge L(\mathtt {B}_n). \end{aligned}$$

(7f)

This formulation was used in [1] for $n=8$ to find the convex small 8-gon of maximal perimeter.

For each $n = 2^s$ with integer $s \ge 2$, one can also construct a convex small n-gon $\mathtt {Q}_n^*$ with the same diameter graph as $\mathtt {R}_{n-1}^+$ but larger perimeter. Using a similar parametrization as in Sect. 3, we can show that

$$\begin{aligned}&L(\mathtt {Q}_n^*) = \max _{\varvec{\alpha }} \quad L(\mathtt {P}_n) = \sum _{k=0}^{n/2-1} 4\sin \frac{\alpha _k}{2}\end{aligned}$$

(8a)

$$\begin{aligned}&{{\,\mathrm{s.t.}\,}}\quad \sum _{k=0}^{n/2-1} \alpha _k = \pi /2,\end{aligned}$$

(8b)

$$\begin{aligned}&\sum _{k=0}^{n/2-2} (-1)^k \sin \left( \sum _{i=0}^{k} \alpha _i\right) = 1/2,\end{aligned}$$

(8c)

$$\begin{aligned}&0 \le \alpha _0 \le \pi /6,\end{aligned}$$

(8d)

$$\begin{aligned}&0 \le \alpha _k \le \pi /3 \quad \forall k = 1,2, \ldots , n/2-1,\end{aligned}$$

(8e)

$$\begin{aligned}&L(\mathtt {P}_n) \ge L(\mathtt {R}_{n-1}^+). \end{aligned}$$

(8f)

The variables $\alpha _0,\alpha _1,\ldots ,\alpha _{\frac{n}{2}-1}$ are defined in Fig. 8. Clearly, $\mathtt {Q}_4^* \equiv \mathtt {R}_3^+$ and $L(\mathtt {Q}_4^*) = L_4^*$.

Fig. 8

Variables $\alpha _0,\alpha _1,\ldots ,\alpha _{\frac{n}{2}-1}$ for $L(\mathtt {Q}_n^*)$: Case of $n=8$ vertices

We solved both Problems (7) and (8) on the NEOS Server 6.0 using AMPL with the solver Couenne 0.5.8, which is a branch-and-bound algorithm that aims at finding global optima of nonconvex mixed-integer nonlinear optimization problems [5]. We have made AMPL codes available in OPTIGON [8].

Table 4 gives the optimal values $L(\mathtt {B}_n^*)$ and $L(\mathtt {Q}_n^*)$ for $n=2^s$ and $3 \le s \le 7$, along with the perimeters of $\mathtt {B}_n$ and the upper bounds $\overline{L}_n$. Couenne took less than 1 second to compute each $L(\mathtt {B}_n^*)$ or $L(\mathtt {Q}_n^*)$ except for $L(\mathtt {Q}_{16}^*)$, which was computed in 36 minutes. The results in Table 4 support the following key points:

• 1. The optimal perimeter $L(\mathtt {B}_n^*)$ for each $n \le 64$ computed agrees with the best value found in the literature.

• 2. For all $n = 2^s$ and $s \ge 3$, $L(\mathtt {Q}_n^*)< L(\mathtt {B}_n) < L(\mathtt {B}_n^*)$, i.e., $\mathtt {Q}_n^*$ is a suboptimal solution.

• 3. As n increases, the fraction $\frac{L(\mathtt {B}_n^*) - L(\mathtt {B}_n)}{\overline{L}_n-L(\mathtt {B}_n)}$ appears to approach a scalar $b^* \in (0,1)$, i.e., $\overline{L}_n - L(\mathtt {B}_n^*) = O(1/n^6)$.

• 4. For $n=8$, $L(\mathtt {B}_8^*) = L_8^*$.

Table 4 Perimeters of $\mathtt {B}_n^*$ and $\mathtt {Q}_n^*$

Table 5 Angles $\alpha _0^*, \alpha _1^*, \ldots , \alpha _{\frac{n}{4}}^*$ of $\mathtt {B}_n^*$

Table 6 Angles $\alpha _0^*, \alpha _1^*, \ldots , \alpha _{\frac{n}{2}-1}^*$ of $\mathtt {Q}_n^*$

The optimal angles $\alpha _k^*$ that produce $\mathtt {B}_n^*$ and $\mathtt {Q}_n^*$ are given in Tables 5 and 6 , respectively. We observe a pattern of damped oscillation, converging in an alterning manner to a mean value around $\pi /n$. For $\mathtt {Q}_n^*$, this observation leads to the following theorem:

Theorem 5

Suppose $n=2^s$ with integer $s\ge 2$. Then there exists a convex small n-gon $\mathtt {Q}_n$ such that

$$\begin{aligned} L(\mathtt {Q}_n)&= 2n \sin \frac{\pi }{2n} \cos \left( \frac{\pi }{8} - \frac{1}{2} \arcsin \left( \frac{1}{\sqrt{2}}\cos \frac{\pi }{n} \right) \right) ,\\ W(\mathtt {Q}_n)&= \cos \left( \frac{\pi }{2n} + \frac{\pi }{8} - \frac{1}{2} \arcsin \left( \frac{1}{\sqrt{2}}\cos \frac{\pi }{n} \right) \right) , \end{aligned}$$

and

$$\begin{aligned} \overline{L}_n - L(\mathtt {Q}_n)&= \frac{\pi ^5}{32n^4} + O\left( \frac{1}{n^6}\right) ,\\ \overline{W}_n - W(\mathtt {Q}_n)&= \frac{\pi ^3}{8n^3} + O\left( \frac{1}{n^4}\right) . \end{aligned}$$

In particular, for $n=4$, $L(\mathtt {Q}_4) = L_4^*$ and $W(\mathtt {Q}_4) = W_4^*$.

Proof

The proof is similar to that of Theorem 1. $\square$

For all $n=2^s$ with integer $s\ge 2$, the diameter graph of $\mathtt {Q}_n$ has a cycle of length $n-1$ plus one pendant edge. We represent some polygons $\mathtt {Q}_n$ in Fig. 9. They are all symmetrical with respect to the vertical pendant edge. In $\mathtt {Q}_n$, the angles $\alpha _0,\alpha _1,\ldots ,\alpha _{\frac{n}{2}-1}$ defined in Fig. 8 are given by $\alpha _k = \pi /n - (-1)^k \gamma$ for all $k = 0,1,\ldots , n/2-1$, with

$$\begin{aligned} \gamma = \frac{\pi }{4}-\arcsin \left( \frac{1}{\sqrt{2}}\cos \frac{\pi }{n}\right) = \frac{\pi ^2}{2n^2} - \frac{\pi ^4}{6n^4} + O\left( \frac{1}{n^6}\right) . \end{aligned}$$

We can show that $L(\mathtt {Q}_n) > L(\mathtt {R}_{n-1}^+)$ and $W(\mathtt {Q}_n) < W(\mathtt {R}_{n-1}^+)$ when $n=2^s$ with integer $s\ge 3$.

Fig. 9

Polygons $(\mathtt {Q}_n,L(\mathtt {Q}_n),W(\mathtt {Q}_n))$ defined in Theorem 5

6 Conclusion

Tighter lower bounds on the maximal perimeter and the maximal width of convex small n-gons were provided when n is a power of 2. For all $n=2^s$ with integer $s\ge 3$, we constructed a convex small n-gon $\mathtt {B}_n$ whose perimeter and width cannot be improved for large n by more than $\frac{\pi ^7}{32n^6}$ and $\frac{\pi ^4}{8n^4}$, respectively.

In addition, under the assumption that Mossinghoff’s conjecture is true, we formulated the maximal perimeter problem as a nonlinear optimization problem involving trigonometric functions and provided global optimal n-gons for $n=2^s$ and $3\le s \le 7$.