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

Aug 2019
9
0
Canada
Hello. :spin:

This is my first post, so sorry for the potential mistakes below.

A grid of dots has the dimensions m by n, where m is greater than or equal to n. Pick k dots from this grid in such a way that they form a polygon with k sides. In other words, no three dots can be collinear

I want to find a function N(k,m,n) that will determine the total number of possible k-sided polygons using m, n, and k. So far, I have only managed to find the formula for k=3 and k=4, both of which are very long and messy, and doesn't really resemble each other. The formulae's accuracy are also somewhat questionable, but their outputs do correspond to the OEIS sequences A194193, A175383,
A262402, and A296367 so there's that. From k=5 onwards, I am more or less clueless.

Here are the links to a desmos graph containing the N3(k=3) and N4(k=4) formulas:

N3
N4

I'll also attach a PDF containing those formulas for easier readability, and a picture showing the grid and some examples.

Any ideas?
 

Attachments

Jun 2019
493
262
USA
Are you only allowing convex polygons? Because concave polygons with k = 5 or higher can have collinear points (think of a five-pointed star formed from a regular pentagon).
 
Last edited by a moderator:
Aug 2019
9
0
Canada
Right - sorry - I forgot about that. Concave polygons are allowed too. So ignore the 'no 3-dot collinear' thing, I guess.

Another thing that I didn't mention in my initial post is that some combinations of dots(starting from k=4) can form more than one polygon. I've attached some examples using k=5.

Also - correct me if I'm wrong, but - some combinations(k=5) can have only 3 dots be collinear but not form any pentagon, like:


. o . o .
o . o. o​

So that's something we'll also have to take into account
 

Attachments

Mar 2015
182
68
Universe 2.71828i3.14159
Only convex polygons are allowed, I think. And "where m is greater than or equal to n" is irrelevant. One side is always greater than or equal to the other side.
Have you checked your answer for m=n=2, k=3 and m=n=2, k=4?
Whats is max(k), given m, n?
 

skipjack

Forum Staff
Dec 2006
21,481
2,470
Is a 5-pointed star acceptable as a polygon?
 
Mar 2015
182
68
Universe 2.71828i3.14159
So ignore the 'no 3-dot collinear' thing, I guess.
It can't be ignored. Maybe you should post the problem, without your words, or any changes made by you.
 
Aug 2019
9
0
Canada
It can't be ignored. Maybe you should post the problem, without your words, or any changes made by you.
Sorry for the misunderstanding - my bad - I made mistakes in the initial post.

What the problem wants is:

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.

In my initial post, I gave links to N3 and N4. Those are functions that are specific to k=3 and k=4, respectively. They are separate functions that give the number of triangles and quadrilaterals using m and n. My goal there is to find the similarities between the two, and hopefully use that to make a function that works for all k: N(k,m,n)

I'll be back in about 3 hrs.:spin:
 

Attachments