Groupe d’études et de recherche en analyse des décisions

G-2020-53

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

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, we formulate the maximal perimeter problem as a nonconvex quadratically constrained quadratic optimization problem and, for \(n=2^s\) with \(3 \le s\le 7\), we provide near-global optimal solutions obtained with a sequential convex optimization approach.

, 18 pages