7
$\begingroup$

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}$:

enter image description here

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}}$:

enter image description here

Placing 4 points at the corners of the square will lead to this path, which I suspect is the longest, with length $3$:

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Fritz Oct 26 '15 at 13:24
  • $\begingroup$ @Fritz Oops, I thought wrong. Will update $n=3$. $\endgroup$ – Element118 Oct 26 '15 at 13:25
  • $\begingroup$ stackoverflow.com/questions/2723626/… $\endgroup$ – mathlove Dec 25 '15 at 10:36
  • $\begingroup$ @mathlove, that was covered in the answer by Fritz. $\endgroup$ – Element118 Dec 25 '15 at 10:58
  • $\begingroup$ 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. $\endgroup$ – Glen Whitney Mar 29 '16 at 23:22
1
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just some thoughts, does this maximise the minimum spanning tree of the points (treating the points as vertices and distances between the points as edges)? $\endgroup$ – Element118 Oct 26 '15 at 13:41
  • $\begingroup$ $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. $\endgroup$ – Fritz Oct 26 '15 at 13:48
0
$\begingroup$

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

$\endgroup$

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.