2
$\begingroup$

How can I tell, how likely it is, that a given convex polygon with a sufficiently high number of edges is random and, if so, what kind of randomness it is (e.g. white noise)?

What is known about the generation of random convex polygons (or polyhedra)?

In view of the comments, I will address the choice of method of generating convex polygons:

  • Take the convex hull of a set of points, that are randomly selected from a convex region; that method appears to be the one, which is understood the best.

  • Starting with a simplex whose corners are randomly selected points, repeatedly cut off a single vertex by a hyperplane that separates that vertex from the rest, until the desired number of vertices is reached.

  • repeatedly and randomly select $n$ points from a random set, until a set in convex configuration is encountered.

While it seems that only the first method is well understood, especially the second method seems suitable for efficiently generating large sets of convex polygons with a predefined number of vertices.

As for the statistical properties, I could imagine

  • distribution of angles between adjacent edges

  • distribution of edge lengths

  • distribution of polygon areas

  • distribution of diameter modality

There are a lot of tests for checking the randomness of a sequence of numbers, e.g. George Marsaglia's Diehard test battery (cf e.g. http://en.wikipedia.org/wiki/Diehard_tests) and I wonder if something in that line could also be devised for a sequence convex polygons.

$\endgroup$
  • 2
    $\begingroup$ Perhaps you need to define what constitutes a "random convex polygon"? If: the convex hull of uniformly distributed points in a disk, then much is known. But one can imagine other definitions. $\endgroup$ – Joseph O'Rourke Dec 14 '14 at 17:12
  • $\begingroup$ For example, one can generate random points on the circle... $\endgroup$ – Igor Rivin Dec 14 '14 at 17:59
  • $\begingroup$ My idea of constructing convex polygons is by starting with a random triangle (i.e. three points randomly chosen on a circle), and then repeatedly randomly choosing a corner and two random values $\alpha,\beta\in(0,1)$ which resemble the proportion, at which the neighboring edges are subdivided to define the triangle to be chopped off. $\endgroup$ – Manfred Weis Dec 14 '14 at 18:09
2
$\begingroup$

I write my comment as an answer because it is a bit longer.

As Joseph O'Rourke indicated, the question needs to be made more precise because it is not clear (to me) what it asks. One way of generating a random polygon is to choose $n$ points independently according to some probability measure on $\newcommand{\bR}{\mathbb{R}}$ $\bR^2$.

For example, if you choose the $n$ random points independently and uniformly in a disk of radius $R$, then an old result of Renyi and Sulanke states that, as $n\to\infty$, the expected number of vertices of their convex hull behaves like $Z (nR^2)^{1/3}$, where $Z$ is an explicit universal constant. In fact, for large $n$, the number of vertices of the convex hull is highly concentrated around its mean. (This is a very general phenomenon; see this paper and the references therein.)

If you choose your $n$ points randomly and uniformly in the interior of a regular convex $r$-gon, then Renyi-Sulanke proved that for large $n$, the expected number of vertices of their convex hull is dramatically smaller, namely it behaves like $\frac{2r}{3}\log n$ as $n\to\infty$. Again,the number of vertices of this random hull is highly concentrated around its mean.

Moreover, in both cases, as $n\to \infty$, the random convex hull becomes highly concentrated near a certain limiting convex region that depends on the concept of randomness you use. (In particular, no chaotic white-noise-like behavior.)

I have mentioned these results to point out that, whatever answers you expect, they will depend on the concept of randomness you use. Hence the need to describe this randomness precisely.

$\endgroup$
  • $\begingroup$ Your answer is probably the best one can get for the interpretation of random convex polygons as convex hulls of point sets, therefore accepted it. Thanks for that nice overview. $\endgroup$ – Manfred Weis Dec 15 '14 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.