A O(n) algorithm for a point set triangulation
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