3
$\begingroup$

Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and every segment is an edge in the tree.

$\endgroup$
1
$\begingroup$

Disclaimer: the proof is quite technical. OTOH, I don't see a comfortable way to do this, because the initial set of segments can be as crazy as possible, even if none of them intersects.

Let's prove that we can make a tree not only from the set of disjoint segments, but also from the set of disjoint trees. So, the initial statement will be just a special case of it when all trees are segments.

The new statement will be proved by downward induction on the number of trees. When we have only one tree, we are done. To make an induction step, it's enough to connect two trees without intersecting or touching other trees.

Define distance between different trees $S$ and $T$ as $d(S, T) = min_{s\in P(S), t\in P(T)}d(s, t)$, where $P(X)$ is a set of all points belonging to tree $X$ (not necessarily vertices), $d(s, t)$ is a usual Euclidean distance.

Then take $(S, T) = argmin_{R, W \hbox{ are trees}, R \ne W} d(R, W)$. Let $d_0 = d(S,T)$. Also define $s$ and $t$ as the points which deliver us the minimum distance.

WLOG $s$ is a vertex. This statement requires some geometrical analysis. The most complicated case is when $s$ and $t$ lie strictly inside some segments. But if so, these segments must be parallel to each other, otherwise we can draw a height from some point to the opposite segment and get a distance smaller than $d_0$. And if they are parallel, the segment $st$ is perpendicular to them both, and we can simply move it to the one of the ends of the segments, so one of points actually becomes a vertex.

First, prove that the segment $st$ doesn't intersect or touch other existing segments. We do it by contradiction. If such segment exists, set the intersection point to $u$. It lies strictly inside $st$, because the tree set is disjoint and not self-intersecting. There is a tree $U$ such that $u\in U$. But either $U \ne T$ or $U \ne S$, thus $d(U, T)$ or $d(U, S)$ is well-defined and is smaller than $d(s, t) = d_0$. Contradiction.

Second, if $t$ is already a vertex, we are done, because we can draw a new segment connecting vertices $s$ and $t$. Otherwise define the segment which $t$ belongs to as $K$.

Third, let's continuously move $t$ on $K$ to one of the ends of $K$. If we reach the end without $st$ touching any other points, we are done. If not, assume that we got a segment $st'$ for $t'\in T$, and also $st'$ contains some other vertex $v \in V$. If there are more than one such vertex, take closest to $s$.

Let's look what happens if $V \ne T$. Geometry says that $st$ is perpendicular to $K$. So, if we draw a height from $v$ to $K$, we get a segment shorter than $st$, and it will deliver a distance from $V$ to $T$ smaller than $d_0$.

And if $V = T$, we can just forget about $t$ and connect $S$ and $T$ using segment $sv$.

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

I'd like to propose a variation on Aleksandr Logunov's proof, that I find to be a bit simpler (arguable).

Let's prove that we can make a tree from a collection of disjoint trees.

So suppose we have a collection of at least two disjoint trees in the plane (if there were only one we would be done).

Without loss of generality, suppose that no two vertices have the same $x$ coordinate (otherwise, just rotate the plane ever so slightly to make this hold).

Choose a vertex $u$ which is the rightmost vertex of some tree but not the overall rightmost vertex (such a vertex necessarily exists if we have at least two trees and no two vertices have the same $x$ coordinate).

Choose a vertex $v$ to the right of $u$. Draw the segment $(u,v]$ and let $S$ be the first segment $(u,v]$ intersects, and $p$ the point of this intersection.

If $p = v$, then we can safely draw the segment $[u,v]$ and decrease the number of connected components in our forest (remember that $v$ is not in the same tree as $u$ because $u$ is the rightmost vertex of its tree).

If $p \neq v$, then let $w$ be a vertex of $S$ to the right of $u$ ($S$ has at least one such vertex). Just like in Aleksandr's proof, we can now move $p$ on $S$ towards $w$ until the segment $(u,p]$ intersects a vertex. We can then safely draw the segment joining $u$ to that vertex and decrease the number of connected components by one.

So we can always decrease the number of connected components by one (if we have at least two to start with) and thus the result follows by induction.

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