Read: path start

Some techniques of drawing random polygons.

A friend and former colleague of mine, Leonard Zusne, wrote a book: Visual Perception of Form Academic Press - 1970. The book was a collection of studies on the psychophysics surrounding the perception of shapes. I recall one study which generated random polygons for use as stimuli in perceptual research: Given a positive integer, n, a collection of n pairs of the form P_i=(alpha_i, d_i) is generated in which 0≤ alpha_i < 2π represents an angle, and d represents a distance from the origin. Borrowing from the terminology of the later-posed art gallery lighting problem, the polygons thus constructed are those lightable by a single lamp. Provided, the center point is located inside the polygon, the polygon has no crossing lines.

P2 Not all polygons are thusly constructable; some require arbitrarily many inside lights. So one is forced to think of other ways to proceed. Chvatal demonstrated in the early 1970's that while all n-gons can be lit with n/3 lights, some do require that many. Alternatively, therefore to generate all n-gons, we could consider positioning n/3 lights randomly in the plane, and then building a star from each. It is not obvious (to me) how we would stitch the various stars together, so this approach seems, at least, at first glance to be doable, but a wee bit unwieldy.

P3 Another way would be to generate n random points in the plane and then figure some way to draw a path through all of them exactly once returning to the beginning, without any crossing lines. There will be on the order of n! different paths through the n points; some will have no crossing lines. How to make sure we sample fairly from all of these, without explicity enumerating them?

Try building a random collection of 7 points in the plane:
Now try a random path through them:

If this is going to be easy I don't see it -- it looks rather like the traveling salesman problem

P4 Another approach might be to find a convex hull H: a convex polygon on k<n points for which the remaining n-k points are all on the interior of H. We may note that if we label the points of H in clockwise order, then no two non-adjacent points in H may be connected. Therefore it seems, the degrees of freedom in the drawing of a simple polygon will be reduced, presumably, therefore, improving our ability to find one.