1
$\begingroup$

I plotted 4 random points on the 2D plane and calculated the shortest and the longest paths joining all 4 points together. The image below shows the longest (blue) and the shortest (black) paths that connects all 4 points in a continuous line. There are totally 6 line segments connecting the 6 possible pairs of points. Only 3 line segments are needed to connect all 4 points. My simulation shows that there are no overlapping line segments for the two paths. Similar results are obtained every time.

Is there any prove to this and has anyone heard of it?

https://i.stack.imgur.com/Bf3OE.png

$\endgroup$
  • $\begingroup$ The image shows only 6 paths which connect 4 points. $\endgroup$ – callculus Apr 7 '18 at 10:38
  • $\begingroup$ There are 2 paths shown in the image, one blue and one black, featuring the longest and shortest paths each connecting all 4 points respectively. Both of these paths has 3 line segments, and the differently colored segments never overlap. $\endgroup$ – Leo Lam Apr 7 '18 at 10:51
  • $\begingroup$ Sorry i haven´t realized that the two different colors. $\endgroup$ – callculus Apr 7 '18 at 11:00
1
$\begingroup$

If some of the lengths are equal (e.g., if the points are vertices of a square), it may happen that a shortest path and a longest path have an edge in common. However, whenever the shortest and longest path are unique, your observation holds.

Note that for any three-edge path running through all four vertices, the complement (=the other three edges) form a path (and not a closed triangle and not a Y-shaped tree). The sum of the length of such a path and of the length of its complement path is of course constant. Thus, there cannot be a path that is longer than the complement of the shortest path, because the complement of that longer path would be shorter than the shortest path.

$\endgroup$
  • $\begingroup$ That's really nice, @Hagen. $\endgroup$ – John Hughes Apr 7 '18 at 11:42
  • $\begingroup$ Thank you very much, @Hagen. Your prove is beautiful! $\endgroup$ – Leo Lam Apr 7 '18 at 11:47

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.