  Triangulation algorithms that conform to a set of non-intersecting input
segments typically proceed in an incremental fashion, by inserting points
first, and then segments. Inserting a segment amounts to: (1) deleting all the
triangles it intersects; (2) filling the so generated hole with two polygons
that have the wanted segment as shared edge; (3) triangulate each polygon
separately. In this paper we prove that these polygons are such that all their
convex vertices but two can be used to form triangles in an earcut fashion,
without the need to check whether other polygon points are located within each
ear. The fact that any simple polygon contains at least three convex vertices
guarantees the existence of a valid ear to cut, ensuring convergence. Not only
this translates to an optimal deterministic linear time triangulation
algorithm, but such algorithm is also trivial to implement. We formally prove
the correctness of our approach, also validating it in practical applications
and comparing it with prior art.
