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