Showing triangulation of equilateral triangle is non-regular

Question

I am trying to show that this triangulation is non-regular (sometimes called non-convex I think). By regular I mean there exists a convex function from the triangulation to $\mathbb{R}$ such that the faces of the lower convex hull of the lifted points correspond to the triangles of the triangulation. Another definition I have seen is that the domains of linearity of the function coincide with the faces of the triangulation.

I know that the way to do this would be to attempt to construct such a function and probably find inequalities going around the triangle, thus reaching a contradiction. However, I can't seem to figure out the way to do this.

To start, I think it is possible to assume that the three inner vertices lie below the three outer vertices but I am not sure why. If this is the case then I can picture in my head how lifting up the outer vertices would cause one of the faces to not be linear but I'm struggling to see how to make this mathematical. Any help would be appreciated.

Answer 1

October 2023 Update:

In July 2020 I gave an answer to the above question about non-regular triangulations. It seemed sufficient at the time, but two and a half years later a much better answer was posted. I'd recommend reading that one first.

For background and more details on the question, see Regular Triangulations And Steiner Points, especially Section 2 and the references. See also notes and material from an MSRI workshop on triangulations, including this note that contains a folklore answer to the OP on pg 3.

Original July 2020 answer:

We can easily prove that the given triangulation is not Delaunay. The figure below show that the circumcircle of $\triangle{DGH}$ contains another vertex C. This violates the condition of a Delaunay triangulation, which is that no circumcircle of a triangle contains the vertex of a different triangle.

The equivalence of a Delaunay triangulation and a convex hull on a paraboloid via a lifting transform is discussed in Gallier and Quaintance's Aspects of Convex Geometry Polyhedra, Linear Programming, Shellings, Voronoi Diagrams, Delaunay Triangulations, in Section 12.4, pgs 332-334. This takes about 2 pages of exposition, so I won't repeat it here. Background, references, and associated topics are discussed in the same chapter (Chapter 12).

There's the possibility, implied by the title of the question, that the diagram is meant to be a triangulation of nested equilateral triangles. Then the polygons $CHGD, CEFH, EDGF$ would be trapezoids, and thus cyclic. We know that a circle lifts to an ellipse (see Gallier and Quaintance), and since an ellipse is planar, the trapezoids would lift to planar faces. The projection back to the plane would not be triangulation and therefore (by the definition given in the question) not regular.

Answer 2

Using the labels as in brainjam's answer, by contradiction, consider a function $$\omega : \{E,D,C,F,G,H\} \to \mathbb R$$ which produces your triangulation by the process which you have described. Let $\hat{\omega} : \mathbb R^2 \to \mathbb R$ be an associated triangulation-piecewise-linear function. We can assume $\omega(F)=\omega(H)=\omega(G) = 0$ since perturbation of $\hat{\omega}$ by affine function will not affect induced triangulation and points $F,H,G$ are affinely independent. The condition that edge $CF$ will appear in triangulation is $\omega(C)>\omega(E)$. Symmetrically, appearance of edges $EG$ and $DH$ equivalent to $\omega(E)>\omega(D)$ and $\omega(D)>\omega(C)$. So we have $\omega(C)>\omega(E)>\omega(D)>\omega(C)$ which is desired contradiction.