Dropping altitudes to achieve nonobtuse planar triangulations: finite or infinite?

Question

Given a planar triangulation of (say) a convex region, imagine the following process to convert it to a triangulation with no obtuse angles:

• Pick an arbitrary obtuse angle at vertex $a$ of $\triangle abc$ and drop an altitude $ax$ from $a$ to the altitude foot $x$ on $bc$.
• If $x$ also lies in another triangle $\triangle dcb$, then add the segment $dx$ to regain a proper triangulation.
• Repeat.

An example is shown below. The triangulation has two obtuse angles, at vertices $3$ and $4$. The left sequence starts by splitting the angle at vertex $3$ with altitude $35$, next adding segment $15$, then dropping altitude $46$ onto $15$, and so on as illustrated. The sequence depicted never terminates.

The right sequence starts by splitting the angle at vertex $4$ with altitude $45$, and quickly terminates.

---

 

---

My question is:

Q1. Is it the case that, for any planar triangulation of (say) a convex region, there is some ordering of the splittings that terminates in a finite number of splittings? Or is there a triangulation for which every splitting sequence never terminates?

Q2. If the answer to Q1 is Yes (there exists some terminating sequence): Is there an algorithm (more efficient than try-all-possibilities) that finds such a terminating sequence?

Incidentally, I know other methods of obtaining a nonobtuse triangulation. Here I am concentrating on this simple procedure.

Answer 1

There is an example for a triangulation with just one obtuse triangle in each step.

In the image, only triangle $A_1A_2O$ is obtuse. With your algorithm we draw altitudes and reach $H_1,H_2,H_3,...$ and always we have only one obtuse triangle (in step i, triangle $A_rH_iO$ where $r$ is the remainder of $i+2$ modulo $6$), so we are forced to draw it's altitude.

Red segments are the altitudes and green segments are the added segments to regain a proper triangulation. So there is a triangulation that never terminates.

Now I introduce an algorithm for a triangulation without any cycle in its adjacency graph.

Consider the adjacency graph of the initial triangulation. (Vertices are triangles and edges are between two triangles with common segment) If this graph is a tree, i.e. there is not a hole in the region or a vertex with 360 degrees (like $O$ in the image) in the triangulation, then we can choose the order of splitting such that the algorithm terminates. Here is the algorithm:

Choose an obtuse triangle ($abc$) and drop its altitude ($ax_1$), add the other segment ($dx_1$), now probably $x_1$ is the obtuse vertex of a new triangle namely $dx_1c$, drop the altitude form $x_1$ in the new triangle ($x_1x_2$), now continue with $x_2$ and drop its altitude, and continue dropping altitudes from new vertices, you never come back to a segment because there is no cycle in the graph, so this procedure ends, now ($abc$) is done and the number of obtuse triangles are less than the the number of initial ones. Repeat this procedure for each obtuse triangle until you are done.