Enumerate unique lattice polygons for a given area using Pick’s Theorem

combinatoricseuclidean-geometrypolygons

Pick's Theorem

Suppose that a polygon has integer coordinates for all of its vertices. Let $i$ be the number of integer points interior to the polygon, and let $b$ be the number of integer points on its boundary (including both vertices and points along the sides). Then the area
$A$ of this polygon is:

$$A = i + \frac{b}{2} – 1$$

Example

Let integer area $A = 5$, these are the possible pairs of boundary $b$ and interior $i$ points that satisfy Pick's

pics

Notice that some pairs $(b,i)$ have multiple unique shapes

6

For $b=6,i=3$ above, found $7$ unique shapes so far. Are there others that I missed? I'm just visually checking and haven't written any code to determine the exact number, yet.

The Pick's integer solutions are

$$\forall A>0, \quad 1 < n \leq (A+1) : b = 2n, \, i = (A + 1) – n, \quad n,A \in \mathbb{Z}$$

Brute-Force Approach

  1. Find all possible pairs of boundary $b$ and interior $i$ points that satisfy Pick's Theorem.
  2. For each $(b, i)$ pair, attempt to generate all unique simple lattice polygons.
  3. Count the unique shapes for the given area $A$.

Question

Given an integer area $A$, I'm curious about how many unique shapes can be formed on a $2D$ lattice?

Best Answer

There are infinitely many unique shapes for any area $A$. Let $A=1$ and we can make triangles with base of 2 and height of 1 and move the top vertex over a lattice point. This can be done for any size base of $2A$ and height 1 for a triangle of area $A$. Add in an interior point and this game can continue for any $i$ you choose also.

enter image description here

And for more interior points, you will move the top green dot along, keeping the rest fixed. Shown are $A = 2,3,$ and $4$, with $i = 1,1,2$ respectively.

enter image description here