Iterated Circumcircle

Question

Take three noncollinear points (a,b,c), compute the center of their circumcircle x, and replace a random one of a,b,c with x. Repeat. It seems this process may converge to a point, assuming no collinearities ever develop along the way. But the dynamics seem complicated, with intermediate growth before ultimate convergence. And I am by no means certain of ultimate convergence, even generically. Here is an example, iterated 1000 times:

Has this or similar processes been studied? Might one establish conditions under which initial triangles definitely lead to convergence?

Reformulation. In light of the many cogent comments, let me attempt a reformulation and sharpening of the question. Restrict attention to isosceles triangles, represented by their apex angle θ and incident side length L. Let T represent the space of all (θ,L) pairs. Color a point of T red if almost surely the process converges to a point, and blue otherwise. What does the coloring of T look like? Are the red points dense in T?

Edit(10Sep10). A knowledgeable colleague believes that the scaling limit of the evolution of $a_n$ in Victor's answer (the isosceles side length) should be Brownian motion on the line. In light of this opinion, I (belatedly) accept Victor's answer. Thanks again for the interest shown in my question!

Answer 1

This problem may be reduced to computation of the Lyapunov exponent of a simple stochastic sequence.

Clearly, all triangles so generated are isosceles. Let $a_n$ be the common length of two equal sides and $2\phi_n$ the angle between them ($0\leq\phi_n\leq\pi/2).$ Then by elementary trigonometry,

$$a_{n+1}=R_n=a_n/2\cos(\phi_n), \quad \phi_{n+1}=\begin{cases}\pi/2-\phi_n,\qquad\qquad\qquad p=2/3 \\ \begin{cases} 2\phi_n \text{ if }\phi_n\leq\pi/4\\ \pi-2\phi_n \text{ if }\phi_n\geq\pi/4\end{cases} \ p=1/3\end{cases}.$$

Therefore, in the triangles shrink to a point (in the sense of their size, regardless of the location), $a_n\to 0$ a.s. if and only if $\prod_n 2\cos(\phi_n)$ a.s. diverges to $\infty.$ If, moreover, the Lyapunov exponent (i.e. the exponential divergence rate) is greater than 1 then the triangles themselves also converge a.s. to a point.

(continued)

The behavior of the stochastic sequence $\{\phi_n\}$ strongly depends on the diophantine properties of $\phi_0.$ There are a.s. finitely many distinct terms if and only if $\phi_0$ is rational, i.e. commensurable with $\pi$. It a.s. contains $0$ if and only if $\phi_0$ is a dyadic rationale: the triangles will a.s. "blow up" after getting 3 collinear points whose circumcenter is at infinity. In the rational case $\phi_0=\pi p/q$ with odd $q$, the stochastic sequence is an irreducible finite Markov chain. The Lyapunov exponent can be computed from the stationary distribution by matrix algebra. For example, if $\phi_0=\pi/6$ then there are two states, $\pi/3$ and $\pi/6,$ the transition matrix is $\begin{bmatrix}1/3 & 1\\ 2/3 & 0\end{bmatrix}$ and the stationary distribution is $(3/5,2/5),$ which yields

$$\lambda=(2\cos\pi/3)^{3/5}(2\cos\pi/6)^{2/5}=3^{1/5}>1.$$

Thus starting with an equilateral triangle, two similarity classes of triangles will occur, equilateral ($\phi=\pi/6$) with $p=2/5$ and $(2\pi/3,\pi/6,\pi/6)$ ($\phi=\pi/3$) with $p=3/5.$ Under the iteration, the smaller side will scale down by factor $\sqrt{3}$ in the equilateral case and stay the same in the obtuse case, with the average shrinkage factor $3^{1/5}.$ I see how to carry out similar analysis in general, but I wouldn't do it here.

On the other hand, from ergodic theory it should follow that for almost all $\phi_0$ the sequence $\{\phi_n\}$ will be equidistributed $\mod \pi/2.$ Observe that $\cos(\phi_n)=\pm\cos(\psi_n),$ where $\{\psi_n\}$ is a stochastic sequence $\mod \pi$

$$\psi_{n+1}=\begin{cases}\pi/2-\psi_n,\ \ \, p=2/3 \\ 2\psi_n,\quad\quad\quad p=1/3\end{cases}.$$

My heuristic computation of the Lyapunov exponent gives

$$\ln\lambda=\frac{1}{\pi}\int_{0}^{\pi}\ln(2|\cos(\psi)|) d\psi=0,$$

so generically $\lambda=1$ and it remains unclear whether the sizes of the triangles go to zero. This will be difficult to see using graphical simulations due to roundoff errors, but with a bit of care, you can numerical simulate the sequence $\psi$ directly, compute $\prod_{k=1}^n 2\cos(\psi_k),$ and study its asymptotics. I have analyzed a similar problem in which you always replace the vertex where two equal sides meet: this corresponds to the deterministic sequence $\psi_{n+1}=2\psi_n$ and the sides do not go to zero, because

$$a_{n}=\frac{\sin(2^{n+1}\psi_0)}{\sin(\psi_0)}a_0.$$

Answer 2

While you might conceivably get convergence a.s., you won't get convergence always, since one could have a sequence where only the vertex not adjacent to the longest edge is replaced. This would force the sequence of diameters to never decrease.

Answer 3

This is also similar to a different technique for generating the Sierpinski Triangle through an iterated method which neither converges nor diverges but chaotically stays in a particular set.

Given any triangle $ABC$ with non-collinear endpoints $A,B,C$, select a random point $P_0$ within the center of $ABC$

then iterate the following

pick any one of the vertices, $A,B,$ or $C$ at random

generate $P_{i+1}$ as the midpoint of the line-segment $P_i$ and the randomly selected vertex

Iterated multiple times, this generates a Sierpinski triangle with a few extra points thrown in at the beginning. If your initial point is definitely on the Sierpinski triangle (say you start with one of the vertices as your initial point $P_0$), then all of the subsequent points are definitely in the Sierpinski triangle. The Sierpinski triangle has Hausdorff dimension $log(3)/log(2)$ ≈ $1.585$ (copied from wikipedia)

I remember writing this as a program in BASIC on the Apple ][, but I cannot recall the source of the question that led me to the program. Most likely it was an article in Byte or Creative Computing.

This is similar to your selecting a new point defined as the circumcenter of your three points, and then using that new point along with two of the vertices of your current triangle to generate then next triangle to find the circumcenter of. Your iterated method leads to points outside of the triangle, leading to a wandering triangle in most cases, leading to your second question, in which cases of initial triangles do you end up with convergence or divergence, which seems to have been addressed with some of the earlier answers. I'll think about that a bit more before commenting on that.

This "iterated line-segment midpoint" technique definitely does not converge. It leads to selecting points within the set of points contained within the Sierpinski Triangle. The new points also do not diverge away; the points always stay within the confines of the triangle $ABC$, and if the initial point is in the Sierpinski triangle, then the set of points generated are all also within the set of points in Sierpinski triangle.

Answer 4

"Similar"? Let's see, how much license does that word give us? Within the past year or so an article appeared in the Monthly that studied a problem like this: take finitely many points in the plane. Form their Voronoi diagram. Look at the set of points where three or more edges of the Voronoi diagram meet. Let that set replace the set you started with. Iterate. They actually got some results. (Otherwise it wouldn't have been published, I suppose.)

Is that "similar" enough?

Answer 5

Here is a geogebra file that can do your construction. Click on the far right tool (TriCircumcenter), then click on three points. A triangle will be made along with its circumcenter.

Just playing around a bit, the convergence seems to heavily depend upon which points are chosen--though maybe random points will produce convergence.

http://www.math.ohio-state.edu/~snapp/IteratedCenter.ggb