A zonogon approach for computing small convex polygons of maximum perimeter
研究在直径不超过1的条件下，寻找具有最大周长的n顶点凸多边形问题，提出基于Zonogon的混合整数非线性规划模型，并给出高精度数值解。
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.