3
$\begingroup$

Suppose one creates a random, closed, likely self-crossing polygon from $n$ unit-length vectors arranged head-to-tail, randomly oriented except for the requirement that their sum is zero (so the polygon closes). Here are some examples, for $n=36$:

      FlipPoly8

Q. What is the expected diameter of such a polygon, as a function of $n$? In particular, what is the expected growth rate w.r.t. $n$?

Perhaps it is expected to be $\sim \sqrt{n}$? Continuing the example above, I see about $1.1 \sqrt{n}$. But that could also be about $0.2 n$ if the growth is linear instead. My limited simulations do not distinguish between square-root and linear growth.

To answer guest's query, I start with a closed regular polygon, and then reflect subchains across the line determined by randomly selected pairs of vertices, until thorough mixing is reached.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ What exactly does 'randomly oriented except for the requirement that their sum is zero' mean, and how are you sampling from that distribution? $\endgroup$
    – guest
    Commented Apr 19, 2014 at 1:17
  • $\begingroup$ @guest: Good question! Maybe I should answer directly in the post... $\endgroup$
    – Joseph O'Rourke
    Commented Apr 19, 2014 at 1:23
  • 1
    $\begingroup$ that sounds like a 2d analogue of the crankshaft algorithm for 3d sampling... did you invent that sampling scheme yourself or find it in the literature? I would guess that if it's in the literature and is proved to be ergodic then they would also give other properties like the one you are requesting $\endgroup$
    – guest
    Commented Apr 19, 2014 at 1:40
  • $\begingroup$ @guest: Invented myself, in ignorance of the literature. :-) $\endgroup$
    – Joseph O'Rourke
    Commented Apr 19, 2014 at 1:44
  • 1
    $\begingroup$ When $n$ grows, the polygon becomes a Brownian bridge (also called Brownian loop). The Brownian bridge is obtained by a linear deformation of Brownian motion. Since the frontier of Brownian motion has Hausdorff dimension 4/3 and as its size scales as $\sqrt n$, a reasonable conjecture is that the frontier scales as $n^{2/3}$. Is that compatible with your simulations ? $\endgroup$
    – Tom-Tom
    Commented Apr 22, 2014 at 21:35

1 Answer 1

Reset to default
4
$\begingroup$

(I post yesterday's comment as an answer and add a remark concernin the area)

When $n$ grows, the polygon becomes a Brownian bridge (also called Brownian loop). The Brownian bridge is obtained by a linear deformation of Brownian motion. Since the frontier of Brownian motion has Hausdorff dimension 4/3 and as its size scales as $\sqrt n$, a reasonable conjecture is that the frontier scales as $n^{2/3}$.

Your algorithm, if it already can identify the frontier, should also be able to compute the enclosed area. There is a result that this area should have expectation value $n\pi/5$ that would be interesting to check ! See the article by Garban and Ferreras.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am puzzled by this answer. I would have expected the diameter to behave like the maximum of partial sums of random vectors of unit length, which would be roughly $n^{1/2}$. Are you saying that the diameter in this case is substantially bigger, just because of the constraint that the end points have to match? Seems quite strange (and interesting of course). $\endgroup$
    – Lucia
    Commented Apr 23, 2014 at 14:40
  • $\begingroup$ @Lucia. The segments of unit length create a shape in the plane, they can intersect each other eventually. Take a point $M$ very far away from the figure. All the points that you cannot reach from $M$ without crossing a segment form a bounded domain $\mathcal D$. The polyogon is the boundary of $\mathcal D$. By perimeter we mean the length of the polygon, which is made of segments of various lengths between 0 and 1. The size or diameter is, form instance, the maximum distance between two points inside $\mathcal D$ and it indeed scales as $\sqrt n$. $\endgroup$
    – Tom-Tom
    Commented Apr 23, 2014 at 21:45
  • $\begingroup$ Indeed. Note that the problem asks about the diameter and not the perimeter. Hence my confusion about your answer. I agree that the diameter scales as $\sqrt{n}$. $\endgroup$
    – Lucia
    Commented Apr 24, 2014 at 3:19
  • $\begingroup$ @Lucia. You are right. Maybe I interpreted the question with the assumption that it cannot be that simple. $\endgroup$
    – Tom-Tom
    Commented Apr 24, 2014 at 8:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .