A zonogon approach for computing small convex polygons of maximum perimeter

Abstract We derive a mixed integer nonlinear programming formulation for the problem of finding a convex polygon with n vertices that is small (diameter at most one) and has maximum perimeter provided a stated conjecture is true. The formulation is based on a geometric construction using centrally symmetric polygons (zonogons). The resulting zonogons can be characterized by equivalence classes (under the action of the dihedral group) of 2 n -vectors with entries either plus or minus one and a self-duality property and we study the number of these codes . We propose a two-phase computational approach. Phase I comprises the solution of a purely combinatorial problem. Under assumption of Mossinghoff’s conjecture of axial symmetry, the Phase I problem can be reduced to a Subset-Sum Problem. Without Mossinghoff’s conjecture, a generalized Subset-Sum Problem needs to be solved, which consists of picking n non-opposing 2 n -th roots of unity such that their sum is as small as possible. Phase II consists of a non-combinatorial Nonlinear Programming Problem. We develop and implement a Lagrange-Newton-type method with multi-precision floating point arithmetic to solve these problems to high accuracy. We provide extensive numerical results including solutions for polygons with 64 and 128 vertices that are accurate to 90 decimal digits.