Before revision:  Inserting a segment amounts to delete all the triangles it intersects , define two polygons that fill the so generated hole and have the segment as shared basis, and then re-triangulate each polygon separately.
After revision:  Inserting a segment amounts to delete all the triangles it intersects , define two polygons that fill the so generated hole and have the segment as shared edge; (3) triangulate each polygon separately.