For me a simple polygon in the euclidean plane just means that it is like a piece of paper. The only constraints are that the paper has to be unfolded, cant have a hole in the middle and can only have straight edges.
So the question is if the optimal solution of the traveling salesman problem for any set of n points is such a polygon.
If it is, I would like to know how fast the number of simple polygons that can be created with n points, grows with n. Espacially in worst case. Up until 10 it grows slower then n^4 for random points so avg case.
If it's not I would like to see a counterexample.
Is there an algorithm to generate all polygons of that kind out of n random points?
It is easy to see (by the triangle inequality applied in two quarters) that the sum of the lengths of the diagonals of any convex quadrilateral is longer than the sum of the lengths of a pair of opposite sides. Consequently, the shortest Hamiltonian cycle through a set of points in the plane does not contain any crossing edges.
$n = 10$ is tiny: $n^4$ looks much larger than $2^n$ on that range, for example. It's easy to construct arrangements of points with on which you can explicitly construct exponentially many noncrossing Hamiltonian cycles (for example: given any arrangement of $n$ points, replace each point with four tightly clustered points; then any noncrossing Hamiltonian cycle in the original graph can be lifted to at least $2^n$ Hamiltonian cycles in the inflated graph) and there is no reason to think that random collections of points have lots of extra constraints.
OTOH there are good approximations for TSP in the Euclidean setting, see https://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean