As a final step in the triangulation, we need to go through all edges that connect two points that are "unrelated" in the sense that the edge is not part of the original graph. We can do this by first making a quadrilateral from the two adjacent triangles by removing the offending edge. Then we split this into four new triangles, introducing a new point in the middle of the edge we removed. The idea is that the result graph should not have any unconstrained edge which touch the boundary in two locations.