How to enumerate unique lattice polygons for a given area using Pick's Theorem?

225 Views Asked by At

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?

2

There are 2 best solutions below

1
On 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

0
On

Complementing N. Owad's answer -- the number of polygons of a given area becomes finite if you consider them up to unimodular equivalence, i.e. up to lattice-preserving affine transformations. The number of convex polygons up to unimodular equivalence with area $1/2,1,3/2,2,5/2,3\ldots$ is $1, 2, 3, 7, 6, 13,\ldots$ -- see https://oeis.org/A187015 and refs. therein, especially Balletti.