# Maximising shortest path passing through $n$ points inside a bounded region

Source:

I was programming a visualization for the Euclidean Travelling Salesman Problem when I stumbled on this problem.

Question:

Consider a bounded region in the Euclidean plane, in this case, we will consider the unit square $[0, 1]\times[0, 1]$.

We will place $n$ points inside it.

Next, we find the shortest path that passes through all $n$ points.

Where do we place the $n$ points such that the length of this shortest path is maximised?

Examples:

For $n=2$, we have the longest path as a diagonal of the square, with length $\sqrt{2}$: For $n=3$, (credit to Fritz for spotting this error) we have this longest path part of the largest equilateral triangle in the square, of length $\frac{8}{\sqrt{6}+\sqrt{2}}$: Placing 4 points at the corners of the square will lead to this path, which I suspect is the longest, with length $3$: Some work:

The maximum length path is $\omega(\sqrt{n})$.

A construction: Arrange the $n$ points into a regular grid formation. Since the points are separated by a distance $\Theta\left(\frac{1}{\sqrt{n}}\right)$ and there are $n$ points, multiplying them gives the bound of $\omega(\sqrt{n})$

Placing the points at $\left(\frac{i}{\lceil\sqrt{n}\rceil}, \frac{j}{\lceil\sqrt{n}\rceil}\right)$ would give a closed-form lower bound for the upper bound of $\frac{n-1}{\lceil\sqrt{n}\rceil}$.

Bounty Edit:

I am interested in closed-form bounds for the upper bound (such as the lower bound of $\frac{n-1}{\lceil\sqrt{n}\rceil}$ as mentioned above). Other bounded regions (such as the unit circle) may be also interesting and will also be considered for the bounty.

• For $n=3$, wouldn't the shortest path be maximized by an equilateral triangle where each vertex touches the 1 unit square? Also, isn't the current set of $(0,1) (1,0) (0,0)$'s shortest path actually just 2 units? Oct 26, 2015 at 13:24
• @Fritz Oops, I thought wrong. Will update $n=3$. Oct 26, 2015 at 13:25
• stackoverflow.com/questions/2723626/… Dec 25, 2015 at 10:36
• @mathlove, that was covered in the answer by Fritz. Dec 25, 2015 at 10:58
• The answer in the case $n = 3$ is still wrong (thanks to Peter Winkler at Dartmouth for pointing this out.) See details in the answer below. Mar 29, 2016 at 23:22

• $n=7, 11, 14,$ or $19$ all could lead to interesting cases since there is at least one circle that is not bound by other circles, but I am being led to believe that since the distance between the centers of touching circles is going to lead to the shortest path, the shortest path is then maximized by having similar circles with the largest radius. I may be wrong, but it seems likely to be optimal. Oct 26, 2015 at 13:48
This is the answer for just $n=3$, because the answer above is still incorrect.
Without loss of generality, you can assume one point is at $(0,0)$ and the other two are $(x,1)$ and $(1,y)$. First assume that the side from $(0,0)$ to $(x,1)$ is not the longest side of this inscribed triangle. Then the maximum shortest path will clearly come when the triangle is isosceles, with the $(0,0)$ to $(x,1)$ side as the short base. In other words, in this case, the shortest path is maximized when $\sqrt{y^2 + 1} = \sqrt{(1-x)^2 + (1-y)^2}$, or $y = (1-x)^2/2$. This situation holds until $x$ gets large enough for the triangle to be equilateral, at $x = 2 - \sqrt{3}$, at which point the situation flips and the shortest path is maximized when $(x,1)$ is chosen so that the triangle is isosceles with shortest side $(0,0)$ to $(1,y)$. That situation is entirely symmetric, so we only have to consider the length of the shortest path on the interval $x \in [0, 2-\sqrt{3}]$. Since $y = (1-x)^2/2$, this length is $\sqrt{(1-x)^4/4 + 1} + \sqrt{x^2 + 1}$. You can use any of a variety of techniques to find the maximum of this on the interval $[0,2-\sqrt{3}]$, e.g. it has one critical point and you can check the values at the endpoints and the critical point, but it turns out to occur at $x=0$ with a path length of $\sqrt{5}/2 + 1$, corresponding to the isosceles triangle with vertices at $(0,0)$, $(0,1)$, and $(1,1/2)$.