[Help] The number of possible k-sided polygons in an m by n grid of dots

skipjack

Forum Staff
Dec 2006
21,379
2,410
The "inner pentagon" in my diagram is ignored because it doesn't use any lattice points. This wouldn't, as you say, comply with your last revision of the rules, but your motivation for the rules is unclear, as you keep changing them.
 
Jun 2019
493
262
USA
My gut instinct is that you're going to have to take connectivity into account for k > 4.

I'm guessing your solutions for N3 and N4 bank on counting the number of non-colinear triplets and quadruplets, respectively? If so, the solution for the larger polygons may be fundamentally different.

Incidentally, a brute force computer code should easily be able to do this for max(m,n) up to 100s if not 1000s or more. If this were my project, I would probably try a parametric study of simulations first, look for patterns, follow two or three red herrings, and then give up and table it for a few decades.
 
Aug 2019
9
0
Canada
That last revision should be the final one - there shouldn't be any other cases left. As long as it forms a simple polygon, it is allowed.
 
Jun 2019
493
262
USA
One last clarification, and I think the rules will be clear for everyone:

1. You have an m by n grid of dots.
2. Pick k dots from the grid
3. Connect the dots to form a k-sided polygon. The connecting line segments cannot intersect each other or pass through another dot. Each dot will only have one line going in and one line going out. See attachment below.
4. Find a function/formula that uses k, m, and n to calculate the total number of distinct k-sided polygons that can be made in this way.
The line segments cannot pass through any other vertex of the polygon, or the line segments cannot pass through any other dot on the m by n grid (other than their own vertices, obviously)?

In other words, would the triangle {(0,0), (0,2), (2,2)} be an acceptable polygon on a 3x3 grid?
 
Aug 2019
9
0
Canada
One last clarification, and I think the rules will be clear for everyone:


The line segments cannot pass through any other vertex of the polygon, or the line segments cannot pass through any other dot on the m by n grid (other than their own vertices, obviously)?

In other words, would the triangle {(0,0), (0,2), (2,2)} be an acceptable polygon on a 3x3 grid?
No.
 
Aug 2019
9
0
Canada
Solutions that include cases where {(0,0), (0,2), (2,2)} is acceptable are welcome as well, though. It's still better than nothing.