Move points in plane to a line via non-overlapping paths

Question

If we have $k$ points in an infinite 2-dimensional real plane, is there an algorithm to "move" those points to some line $L$ in the plane via completely non-overlapping paths? The $k$ points are arbitrarily placed but in unique positions.

Alternatively, the problem can be phrased as connecting each point $p_i$ to a line $L$ via a line segment such that none of the line segments overlap.

Answer 1

Taking @David Sheard's comment and running with it:

Suppose two or more points have the same orthogonal projection onto $L$. Then we can separate these projections $-$ fan them out, if you will $-$ by rotating all the lines by the same angle $\theta$:

• if points $P$ and $Q$ are on opposite sides of $L$, their projections will get shifted in opposite directions;
• if they are on the same side of $L$, then their distances $\ell_P,\ell_Q$ to $L$ must be different, so their projections will get shifted by different amounts $\ell_P\tan\theta$ and $\ell_Q\tan\theta$. The shifted lines won't meet, becaue they are all parallel to each other.

And because the number of points is finite, we can make $\theta$ small enough that no rotated line meets the shifted projection of any other points.