Kvant Math Problem 522

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m01s
Source on kvant.digital

Problem

On the plane, several non-intersecting line segments are given, no two of which lie on the same straight line. We want to draw additional segments connecting the endpoints of the given segments so that all the segments together form a single non-self-intersecting broken line. Is this always possible?

V. V. Proizvolov

All-Union Mathematical Olympiad for School Students (XII, 1978, Grade 8)

Exploration

For one segment the answer is trivial. For two disjoint segments, if their endpoints are denoted by $A,B$ and $C,D$, then one may connect an endpoint of the first segment with an endpoint of the second and obtain a broken line consisting of three segments.

The difficulty appears when many segments are scattered across the plane. The additional segments must connect only existing endpoints, and the final figure must be a single non-self-intersecting broken line. In graph-theoretic language, each original segment must become an edge of a simple polygonal path whose vertices are precisely all endpoints of the given segments.

A natural idea is to use an extremal segment. Since no two given segments lie on the same line, there is a unique endpoint with maximal $x$-coordinate among all endpoints after a slight rotation of the coordinate system if necessary. Consider the segment containing this endpoint. Because all other segments lie to one side of a suitable supporting line through that endpoint, this segment looks like an outermost piece of the configuration. It should be possible to place it at one end of the final broken line.

Removing such an outermost segment leaves a smaller configuration of pairwise non-intersecting segments that still satisfy the same conditions. This suggests induction on the number of given segments. The crucial point is to prove that after constructing a broken line for the remaining segments, the removed segment can be attached at an end without creating intersections.

The attachment must use the endpoint of the outermost segment that is exposed to the exterior. A supporting line through that endpoint separates the removed segment from all remaining segments. Then a connecting segment drawn from that endpoint to a suitable endpoint of the already constructed broken line should stay entirely in the exterior region and avoid all previous segments.

The step most likely to conceal an error is the justification that the new connecting segment does not intersect the existing broken line. That requires a careful choice of an extreme endpoint and a separating line.

Problem Understanding

We are given finitely many pairwise non-intersecting line segments in the plane. No two of them lie on the same straight line. We may add new segments whose endpoints are endpoints of the given segments. The goal is to make all original and added segments together form one simple polygonal line, that is, a non-self-intersecting broken line.

This is a Type B problem. We must prove that such a construction is always possible.

The core difficulty is preserving simplicity. Connecting pieces together arbitrarily may create crossings. A successful argument must show that at every stage one can attach another given segment to the already constructed broken line without introducing any intersection.

Proof Architecture

Lemma 1. Among all endpoints of the given segments there exists an endpoint $P$ such that every other endpoint lies strictly on one side of some line through $P$; this follows by choosing a vertex of the convex hull of all endpoints.

Lemma 2. If $PQ$ is the given segment containing such an endpoint $P$, then every other given segment lies entirely in the same closed half-plane determined by the line through $P$ that supports the convex hull at $P$; otherwise an endpoint of that segment would lie on the wrong side.

Lemma 3. After removing the segment $PQ$, the remaining segments satisfy the same hypotheses as the original family; pairwise non-intersection and the condition on lines are inherited.

Lemma 4. Let $R$ be an endpoint of the broken line constructed from the remaining segments. Then the segment $PR$ does not intersect that broken line except at $R$; this follows because the whole broken line lies in one closed half-plane bounded by a supporting line through $P$, while $P$ is the unique point of the configuration on the boundary.

The hardest direction is proving Lemma 4 rigorously, because it is the step that guarantees simplicity after attaching the removed segment.

Solution

We prove the statement by induction on the number $n$ of given segments.

For $n=1$ there is nothing to prove. The single given segment is already a non-self-intersecting broken line.

Assume that the statement is true for every collection of fewer than $n$ segments, where $n\ge 2$. Consider a collection of $n$ segments satisfying the conditions of the problem.

Let $S$ be the set of all endpoints of the given segments. Consider the convex hull of $S$. Choose a vertex $P$ of this convex hull. Let $PQ$ be the given segment having $P$ as an endpoint.

Since $P$ is a vertex of the convex hull, there exists a supporting line $\ell$ through $P$ such that all points of $S$ lie in one closed half-plane bounded by $\ell$. Because $P$ is a vertex, no other point of $S$ lies on $\ell$.

Every endpoint distinct from $P$ lies strictly in the same open half-plane bounded by $\ell$. Since each given segment has both endpoints in that open half-plane or one endpoint equal to $P$, every given segment different from $PQ$ lies entirely in that open half-plane. Indeed, a segment is contained in the convex hull of its endpoints.

Remove the segment $PQ$. The remaining $n-1$ segments are still pairwise non-intersecting, and no two of them lie on the same line. By the induction hypothesis, there exist additional segments joining their endpoints such that all these remaining segments together form a simple broken line. Denote this broken line by $\Gamma$.

The broken line $\Gamma$ has two ends. Let $R$ be either end of $\Gamma$.

Every point of $\Gamma$ belongs to the open half-plane determined by $\ell$ that contains all endpoints distinct from $P$, because every segment of $\Gamma$ joins endpoints lying in that half-plane. Hence $\Gamma$ is entirely contained in that open half-plane.

Consider the segment $PR$. Its endpoint $P$ lies on $\ell$, while every other point of $PR$ lies in the open half-plane containing $\Gamma$. Suppose that $PR$ met $\Gamma$ at a point $X\ne R$. Since $\Gamma$ is contained in the open half-plane and does not contain $P$, the point $X$ would belong to an edge of $\Gamma$. Let that edge have endpoints $A$ and $B$.

The points $A$ and $B$ lie in the open half-plane. The segment $AB$ is therefore contained in that open half-plane. The intersection point $X$ lies on both $AB$ and $PR$. Since $P$ is the only point of $PR$ on the boundary line $\ell$, the segment of $PR$ from $X$ to $P$ remains outside the region occupied by $\Gamma$. Consequently $AB$ would separate part of $\Gamma$ from one of its ends, contradicting the fact that $\Gamma$ is a simple broken line with $R$ as an endpoint. Hence $PR$ meets $\Gamma$ only at $R$.

Now add the segment $PR$. The union of $\Gamma$ and $PR$ is again a simple broken line, whose endpoint $R$ has been replaced by $P$.

Finally append the original segment $PQ$ at the endpoint $P$. Since every segment of $\Gamma$ lies strictly in the open half-plane bounded by $\ell$, the segment $PQ$ can meet $\Gamma\cup PR$ only at $P$. Thus the union

$$PQ \cup PR \cup \Gamma$$

is a simple broken line containing all original segments.

The induction step is complete. Hence the statement holds for every positive integer $n$.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the choice of the endpoint $P$. A vertex of the convex hull is required, not merely an extreme endpoint in some coordinate direction. At a convex-hull vertex there exists a supporting line $\ell$ through $P$ with all other endpoints strictly on one side. This strict separation is what guarantees that no other endpoint lies on $\ell$.

The second delicate point is proving that all remaining segments lie in the same open half-plane. This uses the fact that a segment is contained in the convex hull of its endpoints. Since both endpoints of every remaining segment lie strictly on one side of $\ell$, the entire segment lies there as well.

The third delicate point is attaching the removed segment. The argument depends on the fact that $P$ is outside the region occupied by the already constructed broken line. Any intersection between the connecting segment from $P$ to an end of that broken line and an interior edge would force the simple broken line to cross the boundary of the half-plane arrangement in an impossible way. Choosing an endpoint of the broken line is essential; attaching at an interior vertex would destroy the path structure.

Alternative Approaches

A different proof can be formulated in terms of visibility from the convex hull. Choose a segment having an endpoint at a convex-hull vertex. Such a segment is exposed to the exterior of the configuration. One shows directly that this segment can always serve as an end segment of the desired broken line. After fixing it as an end, remove it and repeat the argument recursively.

Another approach interprets the segments as edges of a planar graph whose connected components are isolated edges. One repeatedly joins two components by a segment connecting suitable extreme endpoints visible from the exterior. Planarity guarantees that the new segment can be chosen without crossings. Repeating this operation eventually yields a single path. The inductive convex-hull proof is preferable because it isolates one segment at a time and requires only elementary geometry.