4
$\begingroup$

Let $S$ be a fixed set of $n$ points in the plane in general position. Let $T$ be a triangulation of $S$, (somehow) selected uniformly at random from all triangulations of $S$. (There are an exponential number of triangulations,1 somewhere between $2.6^n$ and $43^n$.)

An edge-flip is the operation illustrated below; it requires $e$ to be a diagonal of a convex quadrilateral $Q$.


          EdgeFlip
          (Image from Hanke, Sabine, Thomas Ottmann, and Sven Schuierer.
          "The edge-flipping distance of triangulations." J. UCS 2.8 (1996): 570-579. (PDF).)

My question is:

Q. Starting from $T$, select a random $e$, and edge-flip if $Q$ is convex. Repeat $k$ times, resulting in triangulation $T_k$. As $k \to \infty$, does it remain true that $T_k$ is random, i.e., as if selected uniformly at random from all triangulations of $S$?

This seems almost obviously true, but because the flip operation depends on the geometric structure of the triangulation, it seems conceivable to me that repeated flips bias the triangulations in some way, privileging some over others. Note that there is no edge-flip circumcircle condition here that leads to the Delaunay triangulation. But still the convexity of $Q$ is a geometric constraint.

This is likely well-known, in which case a pointer to the appropriate literature would be appreciated. Thanks!


1Sharir, Micha, and Emo Welzl. "Random triangulations of planar point sets." Proc. the 22nd Annual Symposium on Computational Geometry. ACM, 2006. (PDF.)

$\endgroup$
5
$\begingroup$

It disturbs uniformity. What you have is a Markov chain and it converges to a distribution given by the Perron eigenvector of the transition matrix. To preserve uniformity you need that eigenvector to have equal entries, which will only be the case if the same number of flips are available for each triangulation.

However, there is a simple way to make it preserve uniformity. Each "move" consists of: choose an internal edge at random and flip it if that is legal. Do this $k$ times where $k$ is chosen in advance. The difference is that moves which don't result in flips are counted as well as those that do. Counting flips rather than moves introduces a bias.

$\endgroup$
  • 2
    $\begingroup$ I interpret the question as being the same as the Markov chain described in your last paragraph. $\endgroup$ – Will Sawin Jun 16 '15 at 2:55
  • $\begingroup$ @Will: Yes it can be read that way. $\endgroup$ – Brendan McKay Jun 16 '15 at 5:55
  • 1
    $\begingroup$ I did intend "moves" as Will surmised. So---thanks!---the answer to my question is Yes. And thanks for mentioning the Perron eigenvector. $\endgroup$ – Joseph O'Rourke Jun 16 '15 at 10:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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