How many simple polygons can be made with n points?

1.1k Views Asked by At

You have n points which you can arrange in an infinite 2-D space. What is the maximum number of simple n-sided polygons (i.e. where none of the line segments intersect) which you can create from any one arrangement of all of these points, by using them as vertices?

The upper bound, by considering the permutations is $\frac{(n-1)!}{2}$. However, many of these will be self-intersecting polygons, which are excluded.

If n=3, there is by definition only one triangle.

If n=4 then the upper bound is 3, and this can be easily demonstrated by placing a point in the centroid of three points arranged as an equilateral triangle..

I have an example below of n=5, but I am not sure if there are arrangements with more results:

enter image description here

1

There are 1 best solutions below

2
On BEST ANSWER

You are seeking a bound on the number of simple polygonizations of an $n$-point set. This number is somewhere between $4.642^n$ and $56^n$. In any case, it is $c^n$ for some constant $c$. There has been quite a bit of work on determining $c$. A good source is Erik Demaine's page on this topic.


Twangs
Figure from Damian, Mirela, Robin Flatland, Joseph O’Rourke, and Suneeta Ramaswami. "Connecting polygonizations via stretches and twangs." Theory of Computing Systems 47, no. 3 (2010): 674-695.