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

Question

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.

Answer 1

This actually is making me think that this has some relation to one of my favorite branches of math, packing problems, where you're trying to maximize the distance between all of the points.

A brief search found me this post on cstheory.stackexchange which references one of my favorite Wikipedia articles, Circle packing in a square. Obviously it's a little bit different working with points as opposed to circles, but I think it could help put you on the right path.

Answer 2

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)$.