Proof of correctness for a triangulation-algorithm
I am here again :)
I prove it by induction as you already did. But instead of assuming that the new point is in the lower/upper hull, I assume that the point is the rightmost one (a stronger condition), so it will belong to both, lower and upper hull.
Applying euler formula we know that the total amount of triangles in a valid triangulation is $2\cdot n − h − 2$. Where $n$ is the amount of points and $h$ is the amount of points in the convex hull.
I change a bit the algorithm I proposed you before. Instead of making one sweep from left to right to build the upper hull and one from right to left to build the lower hull, lets build the lower hull with a sweep from left to right too, but this time changing the counter-clockwise condition for clockwise.
Applying the above algorithm to build the triangulation with this slightly new approach will lead you to the same solution. Let's work again on the induction, but this time assuming the new point is the rightmost one and prove the euler condition holds.

Assertion: The said algorithm always returns a triangulation for a given point set.
The assertion is clear for a set of three points, so we got our induction start.
Now lets suppose the assertion holds for all sets with at most n points.
The total number of triangles is $2n - h - 2$
When you add a point in the rightmost position the amount of points will be $n_1=n+1$ and the amount of points in the convex hull will be $h_1 = h + 2 - t$ where $t$ is the total number of added triangles. The total number of triangles we are expecting is:
$$2 \cdot n_1 - h_1 - 2 = 2 \cdot (n + 1) - (h + 2 - t) - 2$$
$$ =(2 \cdot n - h - 2) + t $$
Then the number of triangles that we have built in this last step is $t$ which implies that we have all triangles we need in the solution. Check the picture to get an intuitive idea about what is happening.


I have coded this solution in Codeforces problem, but I can't find it right now :(