A problem in discrete optimization

Question

I am interested in the following problem and its generalizations. Say we are on the real axis, and we have $n$ points $x_1, \ldots, x_n$ on this line. I would like to minimize/maximize the length someone would walk to go through all of them in a certain order.

Intuitively, I feel:

• to minimize, we can pass by all of them from the leftmost one to the rightmost one;
• to maximize, we would need to do many "round-trips", going from a point more on the "left side" to a point on the "right side", etc. but I don't see in what order it is better to do it.

Is there a convenient way to write a proof of the minimization? And how to determine if the heuristic strategy I suggest in the second case works or can be improved.

Less trivially maybe, I am interested in an equivalent question in a two-dimensional disk.

Answer 1

I order the points $x_1<\ldots<x_n$ in this answer.

Your assumption for the minimization is correct. (In fact, if the points are distinct, left-to-right and right-to-left are the only two traversals of minimal length.)

Proof: Given any path which goes through all the points, the portion of its route which starts at one of $x_1$ or $x_n$ will have length at least equal to the distance $|x_1-x_n|$, by the triangle inequality. But the direct linear route you describe has exactly this distance, so it must be optimal.

In the maximization case, things are somewhat more complicated, but the sort of "zigzag" procedure you describe is optimal.

If $n$ is even, then we create a path by connecting $x_i$ to $x_{n+1-i}$ and $x_{n-i}$ for $1\le i<n/2$. We also connect $x_{n/2}$ to $x_n$. This creates a path between all nodes, which I claim is maximal.

If $n=2k+1$ is odd, then we create a path by connecting $x_i$ to $x_{n+1-i}$ and $x_{n-i}$ for $1\le i<k$. We also connect $x_{k}$ to $x_n$. I claim that either this path or its reflection by flipping our indexing of each $x_i$ and performing the same procedure is optimal, depending on whether $x_{k+1}-x_{k}$ or $x_{k+2}-x_{k+1}$ is larger (with the reflection being optimal if the former is larger).

To see why this is true, we count, for each segment between adjacent points in our interval, the number of times we walk across that segment. The total length of our path is just the sum, over each segment, of its length times the number of times we traverse it. The segment from $x_i$ to $x_{i+1}$ can be traversed at most $2i$ times, since we can only go back and forth once each from every one of the $i$ nodes left of it. By the same argument on the other side, the segment can be traversed at most $2(n+1-i)$ times.

Additionally, no segment can be traversed more than $n-1$ times, since there are only $n-1$ segments total, and if any segment is traversed that often, it is unique.

So, for example, if $n=7$ then the number of traversals of each of the 6 segments is bounded above by either $2,4,5,6,4,2$ or $2,4,6,5,4,2$. If $n=8$ it is bounded by $2,4,6,7,6,4,2$.

Then, to see that this path is maximal, we just observe that the described path traces over every segment a maximal number of times, so it is impossible to walk a longer path than they trace out.

Edit: I have included a diagram for $n=8$, to make the idea a little clearer. Above each segment between adjacent points is the number of times the path traverses that segment.

Answer 2

Enumerate the points providing $x_1<x_2<\dots<x_n$.

to minimize, we can pass by all of them from the leftmost one to the rightmost one

Yes, any path going through the points has a fragment connecting $x_1$ and $x_n$. By the triangle inequality, this fragment has length at least $x_n-x_1$. On the other hand, a path $x_1x_2\dots x_n$ has this minimal length.

to maximize, we would need to do many "round-trips", going from a point more on the "left side" to a point on the "right side", etc. but I don't see in what order it is better to do it.

A particular case of this problem (when the distances between consecutive points is equal) was considered by Hugo Steinhaus in his book “A hundred problems”. The solution consists of two pages and I’ll try to read it and adapt to a general case. [Added: I see, RavenclawPrefect already considered this case.]

I am interested in an equivalent question in a two-dimensional disk.

The minimization case is very similar (with the only difference that your path is open, but not closed) to a well-known Euclidean travelling salesman problem, so I expect it has the same computational complexity and can be solved by similar algorithms. I guess for the maximization case you should look for someting like Euclidean longest path problem.