5
$\begingroup$

Let $P$ be a set of three noncollinear points in $\mathbb{R}^2$. Iteratively form the Delaunay triangulation $\cal T$ of $P$, and then augment $P$ by the circumcircle centers of all triangles in $\cal T$, repeating these two steps:

(1) ${\cal T} = \operatorname{DelTri}( P )$.

(2) $P = P \cup \{ x : x \; \textrm{is center of circumcircle of}\; \triangle \in {\cal T} \}$.

It appears that, after a few iterations, $P$ contains either an exactly zero-area triangle of three collinear points, or three nearly collinear points whose circumcircle center lies far outside the initial $P$. For example:


          seed6
          After $5$ iterations, subsets of $3$ nearly collinear points occur.
Starting with an equilateral triangle leads to collinearity in four steps:
          EqTri
          Initial $P$ consists of corners of equilateral triangle.


Q. Is there any initial triangle that does not lead to a $3$-points-collinear or nearly collinear triangle?

By nearly collinear I mean that, as the number of iterations increases, the diameter of $P$ grows without bound: it grows because some triangles become very flat and their circumcenters are cast far away. Truly $3$-points-collinear would throw the circumcenter to $\infty$. I'm asking whether these conditions eventually necessarily occur for any initial triangle.

Added. Just a small amount of data, but $25$ random start triangles with coordinates uniform in $[-1,1]$ each reach a triangle of area smaller than $10^{-10}$ within $10$ iterations.

$\endgroup$
  • 1
    $\begingroup$ What does "nearly collinear" mean? $\endgroup$ – Igor Rivin Oct 9 '17 at 19:44
  • $\begingroup$ Since at the very first step if any of your triangles is acute you are going to get a triangle with an angle $\geq 2\pi/3,$ which, in my book, is pretty close to "nearly collinear"... $\endgroup$ – Igor Rivin Oct 9 '17 at 19:57
  • $\begingroup$ @IgorRivin: Good question, I will edit. $\endgroup$ – Joseph O'Rourke Oct 9 '17 at 20:00
1
$\begingroup$

I don't understand the process well enough to compute it. However, it seems two or more nearly equilateral triangles are created after two iterations.

Consider the map from largest angle of a triangle to largest angle of a triangulation. As seen above, 60 degrees maps to 120. Consider this map over all triangles. This angular map may not be the one you are finally interested in, but a similar map (largest angle of initial triangle to largest angle of resulting configuration) derived from two or four iterations of your process may show you how quickly it blows up.

Gerhard "Angling For Some More Graphics" Paseman, 2017.10.13.

$\endgroup$
  • $\begingroup$ Interesting point, Gerhard. I will think on it... $\endgroup$ – Joseph O'Rourke Oct 14 '17 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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