Proof of correctness for a triangulation-algorithm

Question

I'm working on the following exercise:

Consider a point set $S = \{ p_1, p_2, ..., p_n \}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have pairwise different $y$-coordinates and are sorted in increasing order of them, i.e., $y(p_i) < y(p_j) $ if and only if $i < j$. Develop an algorithm that computes a triangulation of $S$ and needs $O(n)$ runtime and memory.

I got the following algorithm (based on Andrew's monotone chain algorithm) from Marcelo Fornet in his answer to one of my previous questions (I condensed it a bit):

Input: a list P of points in the plane.

Precondition: There must be at least 3 points.

# Initialize T as empty list to store triangulation
Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        Add the last two points from L and P[i] to T (the triangulation)
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from U and P[i] to T (the triangulation)
        remove the last point from U
    append P[i] to U

The triples of points in T will be the triangles

While I understand how this algorithm works I'm struggeling to show it's correctness in a formal way.

My idea would be to use induction on the invariant that this algorithm always prodcuces a triangulation of the given point set. This is what I tried:

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.

But I'm stuck at the induction step. I tried to make a case analysis wether the new point $p_{n+1}$ lies in the upper or the lower half of the convex hull of $\{p_1,....,p_n\}$, but it didn't work out.

I'd be thankful for any kind of help.

Answer 1

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 :(