Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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:
alt text
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!

share|improve this question
    
Make the following series of graphs. Graph 1 : Fix line segment a,b. For each noncollinear c, compute circumcenter x and color c depending on whether a,b,x is a "divergent" triangle. Use area, or distance from a,b, or something else to define "divergent". Hopefully the two-color scheme yields some information. Graph 2a: like Graph 1, then compute c-center y from a,b,x, look at a,x,y, and color c when a,x,y is divergent or not. Graphs 2b, 2c, same as 2a, but using b,x,y or a,b,y. Graph n is the nth iteration. Gerhard "Ask Me About System Design" Paseman, 2010.04.13 –  Gerhard Paseman Jun 14 '10 at 0:04
    
The idea for the above graph series is it may help you find a Mandelbrot-like set. Gerhard "Ask Me About System Design" Paseman, 2010.06.13 –  Gerhard Paseman Jun 14 '10 at 0:06
    
Have you tried the deterministic process where you start with picking three points in order, and then at each step replace the oldest point by the new circumcenter? I'd be curious to know the answer to that maybe simpler problem, too. –  Theo Johnson-Freyd Jun 14 '10 at 2:57
    
Theo, this can be analyzed using the method given in my answer. –  Victor Protsak Jun 14 '10 at 7:44
    
I've seen a related, but certainly not identical, deterministic process defined in terms of the circle inscribed in the triangle formed by the three points: maths.warwick.ac.uk/%7Empollic/inscribed.pdf –  Ian Morris Jun 14 '10 at 9:11
show 1 more comment

5 Answers

up vote 10 down vote accepted

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.$$

share|improve this answer
    
I'm a bit confused as to why $\phi_n$ is distributed over $[0,\pi/2]$ and $\psi_n$ is distributed over $[0,\pi]$. Is this a mistake, or have I missed something? –  Ian Morris Jun 14 '10 at 9:21
    
It's not a mistake. For $\phi_n$, that follows from its definition (half the angle in a triangle). For $\psi_n$, since the absolute value of the cosine function is $\pi$-periodic, so we only need to keep track of $\psi_n (\mod\pi).$ –  Victor Protsak Jun 14 '10 at 10:22
2  
@Victor: Thanks for your perspicacious analysis! "and it remains unclear whether the sizes of the triangles go to zero"---I gather this means it is unclear whether e.g. nearly all triangles converge? –  Joseph O'Rourke Jun 14 '10 at 12:03
2  
(I am getting fed up with rewriting this comment due to typos...! Third time lucky....) We can write $\sum_{k=1}^n \ln |2\cos \psi_k|$ as an ergodic sum with respect to a transformation of $\{1,2\}^{\mathbb{N}}\times [0,\pi]$, (where the first co-ordinate corresponds to the stochastic choice at each stage) so I think that it follows from G. Atkinson's theorem on cocycle recurrence that $\prod_{k=1}^n |2\cos \phi_k|$ generically diverges, accumulating at both 0 and $\infty$. –  Ian Morris Jun 14 '10 at 12:07
    
@Joseph: You are most welcome! It's a nice little problem. You are correct, when I wrote it I didn't see a way to prove or disprove it, although I $\textit{suspected}$ that iterations a.s. do not converge (because the size needn't go to $0$). I would defer to Ian, who is much more competent in this area than I, for the final pronouncement. –  Victor Protsak Jun 15 '10 at 4:47
show 1 more comment

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.

share|improve this answer
add comment

"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?

share|improve this answer
    
"Dynamical System Using the Voronoi Tessellation," 117(2) 2010. Yes, quite related--Thanks! But doesn't seem to shed direct light on the specific process I've defined. I need to study this further... –  Joseph O'Rourke Jun 14 '10 at 2:02
add comment

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.

share|improve this answer
    
actually, this iterated process generates points within the set of points contained in the affine transform of the Sierpinksi triangle onto the triangle $ABC$. –  sleepless in beantown Sep 10 '10 at 13:44
add comment

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

share|improve this answer
1  
Interesting, but I don't know how numerically reliable that simulation is: on my first run, the second triangle turned out to be exactly a right triangle (so all subsequent triangles are right triangles unless you pick 3 collinear points); on my fourth run, I couldn't see the circumcenter of the second triangle (presumably, because the center was off screen due to obtuseness). –  Victor Protsak Jun 14 '10 at 1:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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