# How to connect line segments to form the least number of paths

I have a list of unordered line segments, some of whose endpoints lie on the same point. How do I connect these segments efficiently to form a minimal amount of paths?

For example, if I have the following lines $$(x_1, y_1, x_2, y_2)$$: [[0, 0, 2, 2], [4, 0, 2, 1], [2, 2, 4, 0]] the algorithm should be able to join these three segments into one path $$(x, y)$$: [[0, 0], [4, 0], [2, 1]].

• Can you tell us the context in which you encountered this task? – D.W. May 19 at 4:14
• This is something that could be very handy for a traveling salesman who wants to minimize travel distance! – Pål GD May 19 at 7:28
• Yes, that's right. The specific application I need this for is for generating code for a 3D printer. A single connected line is a lot faster to traverse because the third axis (which moves a lot slower) doesn't need to be used (and travel distance in general is reduced) – Chrisstar May 19 at 7:56