Problem Formulation

This formulation is one of two described by Prieto [1]. It is easy to visualize, and has advantages in later examples. The pentagon is about the smallest model which can reasonably be used – it is non-trivial but is still just about small enough to be written out in full.

Figure 2.1: Polygon Example

One vertex (the highest-numbered, V_N) is chosen as the "base" point, and all the other vertices are measured from it, using (r,θ) coordinates – that is, the distance ("r") is measured from the vertex, and the angle or bearing of the vertex ("θ") is measured from the X-axis.

We shall use r_i and θ_i as the coordinates of vertex V_i. Then simple geometry and trigonometry gives:

• The area of the triangle V_NV_iV_j: area(V_NV_iV_j) =

  1

  2

  · r_i · r_j · sin(θ_j-θ_i)
• The side V_iV_j is given by: (V_iV_j)² = r_i² + r_j² - 2·r_i·r_j·cos(θ_j-θ_i)
• The total area of the polygon is: ∑_i=2^N-1 area(V_NV_iV_i-1)
• The maximum diameter of 1 requires that all the sides of all the triangles are ≤ 1 – that is:
  r_i ≤ 1 for i=1,...,N-1
  and
  V_iV_j ≤ 1 for i=1,...,N-2, j=i+1,...,N-1

We have assumed in the diagram Polygon Example and in the formulation that θ_i≤θ_i+1 – in other words, the vertices are in order anti-clockwise. In fact, this is not just an assumption, and we need to include these constraints as well.

In the diagram, we have assumed that the first angle θ₁ is ≥ 0. This is not an additional restriction if we use the normal modeling convention that all variables are non-negative. We also assumed that the last vertex is still "above" the X-axis – that is, θ_N-1 is ≤ 180° (or π radians).

The requirement is therefore:

Reference:
(1) F.J. Prieto. Maximum area for unit-diameter polygon of N sides, first model and second model (Netlib AMPL programs in ftp://netlib.bell-labs.com/netlib/ampl/models).