Connecting the dots

[DrJones]

Many days ago, I had a dream in which I had to pass a chain through a certain number of rings, placed in different places of a room. The chain's lenght was limited, so there was only one way to reach all rings, starting and ending on the same spot. I had to perform this same task on many other rooms.

When I awoke, I found that I dreamed with the 'traveling salesman problem'. In my dream, I realized two things about the problem, which since then I have been trying to prove/disprove, without success.

1.
Let's say that there are 8 points located in different coordinates of a 10 x 10 grid. I want to join all the dots with straight lines, starting and ending on the same point, and without visiting the same spot twice. Let's call H the group of resultant polygons which comply with that.

Then I think that the polygon on H with the minimum perimeter length doesn't have any crossed line.

2.
Let's say that a polygon has a "sharp end" when there are three consecutive points in it (let's call them A, B, C, where A is connected to B, and B is connected to C) that comply that if we trace a straight line from A to C, that line would "cut" (pass through) the inner side of the polygon (tangencies don't count).

Then I think that, being P the polygon on H with the minimum perimeter length, and being N the number of "sharp ends" on it, there is no other polygon on H with M "sharp ends", where M<N.

I would love if anyone could prove if I'm right or wrong. Thank you.

[DrJones]

Well, just want to inform that I have discovered that the first part is true. Good to know.

[Bicho the Inhaler]

If I've understood correctly, I don't think (2) is correct. Let the points be
A = (0,1), B = (1,1), C = (1,0), D = (0,0),
E = (0,4), F = (4,1), G = (1,-3), H = (-3,0).
Then the cycle AEBFCGDH has 4 "sharp ends" and length 12 + 4sqrt(10) > 24 (since sqrt(10) > 3).
I *think* the shortest cycle, though, has length 24 (AEFGHDCB), which has 5 sharp ends, and I can't see anything as good with 4 or fewer sharp ends (currently without proof).

Edit: Oops, never mind. there are paths of length 24 with only 4 sharp ends, like ABFGCDHE.

Edit 2: I labeled the vertices wrong!

I agree about the first part, though.

[Bicho the Inhaler]

Aha. So that didn't work, but I think it can be fixed. Let c be some positive number. Let's revise the set:
A = (0,1), B = (1,1), C = (1,0), D = (0,0),
E = (0,c+1), F = (c+1,1), G = (1,-c), H = (-c,0).
(My previous attempt was the case c = 3.)

I claim that for large enough c, all shortest circuits have 5 sharp ends, while there are paths with 4 sharp ends. Some 4 sharp end paths are AEBFCGDH and ABFGCDHE, as before. The path AEFGHDCB has 5 sharp ends, and I claim that's the best path, and the only one up to rotational symmetry. This is because if c is very large, the shortest path always visits the vertices A,B,C,D consecutively in some order, since the distance between any pair of those vertices is negligible (of order 1) compared to the distance between any other pair of vertices (of order c), so it is never to the path's advantage to visit {A,B,C,D} twice. Indeed, unnecessary visits can be eliminated: if it goes from X to {A,B,C,D} to Y (X, Y not in {A,B,C,D}), then just going from X to Y is faster by the triangle inequality (in the limit as c -> infinity), and whichever of {A,B,C,D} we skip we just absorb into another visit to {A,B,C,D} (there must be one, by assumption) at negligible cost. So it suffices to consider {A,B,C,D} as a single vertex (say, "V"), and find the shortest tour of {E,F,G,H,V}. It's not hard to see that this must be VEFGH (or a rotation by 90 or 180 degrees). Going back to the original set, it's not hard to see that the actual edges traversed must be DCBAEFGH, which is what we claimed.

I think it actually suffices to take c = 4 (or any c > 3?); 3 was just a bad choice.

[DrJones]

Thank you. I had so far discovered that some polygons with more "sharp ends" had less length than others with fewer, but couldn't find any example with fewer than the best path.