Minimum Area of a Convex Grid Polygon

A symmetrical convex grid polygon is a polygon such that:

All its vertices have integer coordinates.
All its internal angles are strictly smaller than $180^\circ$.
It has both horizontal and vertical symmetry.

For example, the left polygon is a convex grid polygon which has neither horizontal nor vertical symmetry, while the right one is a valid symmetrical convex grid polygon with six vertices:

Define $A(N)$, the minimum area of a symmetrical convex grid polygon with $N$ vertices.
You are given $A(4) = 1$, $A(8) = 7$, $A(40) = 1039$ and $A(100) = 17473$.
Find $A(1000)$.

This problem is a mathematical conjecture and as of this moment, there is no known explicit formula to calculate $A(N)$ for a general $N$. The values given for certain $N$ were likely obtained through computer simulations or exhaustive search, not through an analytical method. The property of symmetry greatly constrains the shape, but doesn’t seem to provide a clear path to an explicit formula for $A(N)$.

A symmetrical convex grid polygon with $N$ vertices is also known as an $N$-agon. The given problem requires finding the minimum area of such an $N$-gon with both horizontal and vertical symmetry. Intuitively, we can think of this minimized area as the result of ‘efficiently packing’ these $N$ vertices into a symmetrical shape on an infinite grid.

Assuming this problem refers to a simple (non-intersecting) polygon with vertices at integer grid points, this is a very complex problem even for standard polygons, let alone polygons with specified symmetries. In computational geometry, this type of problem is called the “Minimum Polygon Problem”, the “Minimal Convex Partition Problem” or the “Polygonization Problem”. Most computational solutions use methods like linear programming, dynamic programming or combinatorial optimization algorithms, and are certainly not trivial.

As for the specific problem of finding $A(1000)$, unless given more data points, all we can currently do is to make estimations or educated guesses based on the given data and hope that a pattern emerges. However, these could be highly inaccurate for such a high number as $1000$.

Note that this problem might be suitable as a computer programming competition problem or a research problem in computational geometry, but it definitely goes beyond typical math tutoring or school homework problem.

More Answers: