# Triangulation of disjoint line segments

Given a set of disjoint line segments in the plane, prove (or disprove) that you can always join the line segments to make a near-triangulation where the vertices are the endpoints of the segments, the outer face is a cycle and every segment is an edge of the triangulation.

• Are degenerate triangles allowed? – HEKTO Dec 10 '19 at 21:53
• I don't think degenerate triangles are allowed here.. all the faces except the outer face must be a triangle. That is called near triangulation – AlgorithmUser785 Dec 10 '19 at 23:48
• @AlgorithmUser785 - there is a simple counterexample in this case: a set of collinear disjoint line segments - it'll be impossible to create any non-degenerate triangle for this set – HEKTO Dec 11 '19 at 0:22

Name the set of segments $$S$$. First, forget about segments and build any triangulation $$T$$ of all endpoints of $$S$$. Then repeat the following process for all segments one-by-one:
If $$e \in T$$, we are done with this step. Otherwise, remove all edges of $$T$$ having an interior intersection point with $$e$$. One can see that it will unite some triangles of $$T$$ into one polygon. Add $$e$$ to $$T$$; it will break this polygon into two smaller polygons. Triangulate them both and add needed edges to $$T$$.
The key point is that if $$e \in S$$ was added to $$T$$, it will never be removed, because segments in $$S$$ don't have interior intersection points. So, after this process $$S \subset T$$.