Consider a convex polygon V_n with n sides, perimeter P_n, diameter D_n, area A_n, sum of distances between vertices S_n and width W_n. Minimizing or maximizing any of these quantities while fixing another defines ten pairs of extremal polygon problems (one of which usually has a trivial solution or no solution at all). We survey research on these problems, which uses geometrical reasoning increasingly complemented by global optimization methods. Numerous open problems are mentioned, as well as series of test problems for global optimization and nonlinear programming codes.

(Joint work with Charles Audet and Frédéric Messine)

References

[1] C. Audet, P. Hansen, B. Jaumard, G. Savard, A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Mathematical Programming, Series A, 87 (2000) 131-152.

[2] C. Audet, P. Hansen, F. Messine, The small octagon with longest perimeter, Journal of Combinatorial Theory, Series A (to appear)

[3] C. Audet, P. Hansen, F. Messine, Quatre petits octogones, MATAPLI 80 (2006) 39-59

[4] C. Audet, P. Hansen, F. Messine, S. Perron, The minimum diameter octagon with unit-length sides: Vincze's wife's octagon is suboptimal, Journal of Combinatorial Theory, Series A, 108, 63-75, 2004.

[5] C. Audet, P. Hansen, F. Messine, and J. Xiong, The largest small octagon, Journal of Combinatorial Theory, Series A, 98(1), 46-59, 2002.

[6] C. Audet, P. Hansen, F. Messine, Extremal problems for convex polygons, Journal of Global Optimization, 2007 (to appear).

[7] C. Audet, P. Hansen, F.Messine, Isoperimetric polygons of maximal width, submitted to Discrete and Computational Geometry.