3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are degenerate triangles allowed? $\endgroup$ – HEKTO Dec 10 '19 at 21:53
  • $\begingroup$ 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 $\endgroup$ – AlgorithmUser785 Dec 10 '19 at 23:48
  • $\begingroup$ @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 $\endgroup$ – HEKTO Dec 11 '19 at 0:22
1
$\begingroup$

This task interested me, at least in non-degenerate case. I've tried to google it and suddenly found a beautiful approach described here (starts with "Next, the constraints are added to the Delaunay triangulation...", but we don't care about Delaunay here).

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.