A O(n) algorithm for a point set triangulation

Question

I'm currently stuck at the following task:

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 found out how to triangulate monotone polygons, which is pretty close to the task, but I don't know how to transfer this into a triangulation of point sets in case the monoton polygonial has a "notch".

I'd be thankful for any kind of help.

Answer 1

You can find one triangulation similar to finding the convex hull. On your conditions finding the convex hull can be solved in linear time.

In order to find the convex hull of a set of points in $R^2$ let's do two sweep lines, one from left to right to compute the upper-hull and another from right to left to find the lower-hull. In order to illustrate the algorithm better I will use pseudo from here.

I'll augment it to solve the triangulation problem. My comments start with #

Input: a list P of points in the plane.

Precondition: There must be at least 3 points.

# We can skip this since points are already sorted 
Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

# 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 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 L and P[i] to T (the triangulation)
        remove the last point from U
    append P[i] to U

Remove the last point of each list (it's the same as the first point of the other list).
Concatenate L and U to obtain the convex hull of P.
Points in the result will be listed in counter-clockwise order.
# Triple of points in T will be the triangles