11
$\begingroup$

Let $P$ be a simple polygon defined by $n$ unit-length segments connecting lattice points of $\mathbb{Z}^2$. I have two operations that preserve the perimeter of $P$. The first is the "pop" of a corner either inward or outward; the second is pushing in a 3-edge "tab" at one spot and immediately pushing out a tab at another. Both operations are only applied if they preserve simplicity (non-self-intersection):

          LatticePolygonMoves
My question is:

Q. What is the limit shape of $P$ as $n \rightarrow \infty$ and the operations are applied randomly for sufficiently many iterations?

I realize this question is imprecise. Perhaps the limit shape depends on the frequency balance between the two operations, which I have not specified. In addition, I am not quite sure how to best to describe a shape. But even an intuitive answer would be useful: Will the shape tend toward a convex-like blob, or toward a more spidery shape? (My guess is the latter.)

I was hoping to get a sense with small experiments as below, but it may require much larger $n$ and many more iterations for a clear pattern to emerge. I would appreciate any help in sharpening the question, answering it in some form, or pointers to related literature that could shed light on the issue. Thanks!

Animation of 200 operations, starting from a crenellated square. The green dot is the centroid of the vertices.           MorphingAnim

Improve this question
$\endgroup$
4
  • $\begingroup$ I think the first picture is not correct (?) and the second rule changes perimeter (?). One possible idea is to represent a configuration as a word ($a^{\pm 1}$ for horizontal edges, $b^{\pm 1}$ for vertical edges). Your substitutions give some rewriting rules $ba\leftrightarrow ab$, (if I understand your first rule correctly) and $a\leftrightarrow bab^{-1}$, $b\leftrightarrow aba^{-1}$, and you want to look at the limit words. $\endgroup$
    – user6976
    Commented Nov 30, 2011 at 1:26
  • $\begingroup$ @Mark: Thanks for catching that; fixed the corner-pop move. I didn't explain the other move well: it pushes a 3-edge tab down to one edge, and elsewhere pops up an edge to a 3-edge tab. Cool idea to view it as symbol rewriting and limit words! Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Nov 30, 2011 at 1:49
  • 2
    $\begingroup$ What you are constructing is van Kampen diagrams over the grouppresentation $ab=ba$. Your moves amount to adding and removing cells (squares) of the diagram. Random diagrams have been considered, say, here: Myasnikov, Alexei; Ushakov, Alexander Random van Kampen diagrams and algorithmic problems in groups. Groups Complex. Cryptol. 3 (2011), no. 1, 121–185. Random diagrams do look "spidery". $\endgroup$
    – user6976
    Commented Nov 30, 2011 at 2:23
  • $\begingroup$ @Mark: Thanks for the key term "van Kampen diagrams" (which I did not know) and the reference, which I will explore! $\endgroup$
    – Joseph O'Rourke
    Commented Nov 30, 2011 at 2:29

3 Answers 3

Reset to default
7
$\begingroup$

Following up on Nathanael's answer: let me give a more precise statement about the dynamics as I understand it. At each step, choose whether you want to pop or push/unpush, then pick a location (or two in the push/unpush case) on the loop at random, and only then look if the operation you want to perform is legal or not (in particular, only then look at whether the loop has a corner at the selected location); if it is, perform it, if not, do nothing.

This is as opposed to the other natural version, which is if you want to pop, pick a place where it can be done at random and do it there - then I have no idea what happens.

The main difference is that with the first option, it is easy to check that the uniform measure is reversible for the dynamics, and hence in particular it is invariant. Then the question is mapped to one of irreducibility, i.e. to a deterministic question: can you, from any given shape, deform it into any other by a sequence of legal moves ? If you can, then indeed the chain converges in distribution to the uniform measure; if you can't, then it becomes a lot trickier. If it is indeed irreducible, then it might provide a good way to generate a self-avoiding polygon at random!

One reference on a very related topic is Sokal's work on the "pivot algorithm" for the SAW (where if you are not careful about exactly which moves are available, the chain is not irreducible and there are frozen configurations).

Improve this answer
$\endgroup$
3
  • $\begingroup$ @Vincent: Thanks for your illuminating comments! My implementation is following your second "natural version," but of course I could change that. Indeed my goal is to generate random SAPs. And indeed, all shapes are connected by legal moves. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 2, 2011 at 12:54
  • 1
    $\begingroup$ One quick note - if you define the second "natural way" appropriately, the distribution of the first move that is actually performed will be the same in both cases. That involves computing the number of legal moves of each type before deciding whether you want to pop or push though... but it should speed up the algorithm. Second note - Tom Kennedy did a lot of simulations of SAWs, he should know more about things like convergence times. $\endgroup$
    – Vincent Beffara
    Commented Dec 2, 2011 at 13:57
  • $\begingroup$ @Vincent: Thanks again, these connections are very useful! $\endgroup$
    – Joseph O'Rourke
    Commented Dec 2, 2011 at 18:10
4
$\begingroup$

The closest thing that comes to mind is the uniform measure on (self-avoiding) polygons with given perimeter. For this there are numerous predictions by physicists: eg, it should be related in the scaling limit to SLE with $\kappa= 8/3$ and so have a fractal dimension of $4/3$

Here the uniform measure is not (or at least, not obviously) the invariant measure of the chain, but maybe on sufficiently large scales it is not so different?

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Nathanael: Thanks for mentioning the connection to the Schramm–Loewner Evolution (SLE)! $\endgroup$
    – Joseph O'Rourke
    Commented Dec 1, 2011 at 1:38
  • $\begingroup$ @ Vincent : Thanks ! The version you suggest is indeed more natural in that it is easy to check the uniform measure is reversible. There should be a way to say that the invariant measures of both chains are pretty similar! (ps. sorry the comment doesn't really fit here but that's the only place MO will allow me to add a comment ... ) $\endgroup$
    – Nathanael Berestycki
    Commented Dec 2, 2011 at 22:28
2
$\begingroup$

Sometimes models like this can simplified e.g. loop erased random walk and self-avoiding walk. Your model may even be integrable if you allow for a small amount of self-intersections.
enter image description here

There are certainly lots of 2D growth models (e.g. Laplacian growth) and they all tend to fall into the KPZ universality class. However, we ought to prove that your model also falls in this class. And maybe there already exists theorem which accomplishes as much. The notes certainly say "ballistic deposition" (as of 2012) is unknown. [1]

It may be helpful to use a small amount of topology here. Your curve is always contractible so that

$$ \gamma \equiv 0 \in H_0(\mathbb{R}^2) $$

and I'm phrasing it in this rather pretentious way in order emphasize that your model is equivalent to adding squares at random from the interior inside the boundary or vice versa.

Homology is clearly not refined enough to detect curvature (in the "hydrodynamic" limit). I already suspect there can be no limit shape at all. If I start with a perfect circle, we're gently adding bits of curvature everywhere, there's no reason why these should perfectly cancel out globally.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

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