Generating random polygons with given vertices

The problem of generating "random" geometric objects is motivated by the need to generate test instances for geometric algorithms. We examine the specific problem of generating a random cursive chi-monotone polygon on a given set of n vertices. Here, "random" is taken to mean that we select uniformly at random a polygon, from among all those cursive chi-monotone polygons having the given n vertices. We give an algorithm that generates a random monotone polygon in O(n) time and space after O(K) preprocessing time, where n < K < n² is the number of edges of the visibility graph of the cursive chi-monotone chain of the given vertex set. We also give an O(n³) time algorithm for generating a random convex polygon whose vertices are a subset of a given set of n points. Finally, we discuss some further extensions, as well as the challenging open problem of generating random simple polygons.