Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. (Then the convex hull of $\Gamma([0,1])$ contains $S$ by the Krein-Milman Theorem.) Let $|\Gamma|$ denote the arc length of $\Gamma$ defined in the usual way.

For a given such $S$, what is the smallest possible value of $|\Gamma|$?

Let $C(S)$ is the circumference (perimeter) of $S$.

Is it true that for all $S$ and $\Gamma$ satisfying the above conditions, $|\Gamma|\ge C(S)$?

Obviously, there is a $\Gamma_0:[0,1]\to \mathbb{R}^2$ with $|\Gamma_0|=C(S)$, so if this last question is answered affirmatively, then we have found the minimum length curve.

Simplified Question: If $S$ has finitely many extreme points, it's a convex polygon. In this case, the question reduces to: Is the shortest cycle visiting all vertices of a convex polygon its perimeter path?

Comment: This seems like a really fundamental and basic question that surely has been asked and answered and would appear as a basic theorem in textbooks on related subjects. But I can't find its answer.

  • $\begingroup$ Here is a related question, but it's not quite the same, because I do not restrict $\Gamma$ to be simple. $\endgroup$ – Will Nelson Dec 20 '13 at 0:47
  • $\begingroup$ But if $\Gamma$ is not simple, e.g. $\Gamma(a) = \Gamma(b)$, why not "cut out" the part of the curve between $a$ and $b$? And the resulting curve has to be shorter. $\endgroup$ – Stephen Montgomery-Smith Dec 20 '13 at 1:16
  • $\begingroup$ @StephenMontgomery-Smith What if there's an extreme point $e=\Gamma(c)$ with $a<c<b$? The modified curve might not pass through $e$. That's not to say that trying to modify a given $\Gamma$ until it's simple is not a bad approach to solving the problem. Maybe it'll work. I'm just saying I don't see how you can make these modifications while ensuring $\Gamma$ still passes through all extreme points. $\endgroup$ – Will Nelson Dec 20 '13 at 2:00
  • $\begingroup$ is not that impossible since $S$ is convex? $\endgroup$ – hbm Dec 20 '13 at 2:05
  • $\begingroup$ I see your point. I was assuming that the curve could not pass through the interior of the convex set. And I'm sure that this must be true. But it needs to be proved. $\endgroup$ – Stephen Montgomery-Smith Dec 20 '13 at 2:06

Partial answer: Finite polygon. There may be errors: I'll leave it to someone else to correct, but I think it's correct.

1) There is a sequence of points within $(P1,P2,...)$ that are touched by the curve in succession. We call this the path point sequence. For instance, the path might go $P1,P2,P3,P2,P1$ for a triangle. Since the curve is finite, and we can assume that the path doesn't have adjacent repitition (i.e. $P1,P1,P1$) this sequence is finite.

2) With no loss in generality, the paths between these sequence points must be straight, since this is the quickest way.

3) Every such path must touch every point (P1,P2,...) at least once. We can assume (that except for the starting point which is touched twice) every point is touched ONLY once. Why? Say we have path point sequence $(...),Px,(...),Py,Px,Pz$. This path can be replaced by $(...),Px,(...),Py,Pz$ by going direct from $Py$ to $Pz$. This path must be strictly shorter $Px$ cannot be on the line from $Py$ because only two extreme points can be on the same line.

4) So excluding the first point, the path point sequence is a permutation of the points. We need only prove this permutation is cyclic.

5) Say that the path point sequence is not cyclic. This means that the path must cross itself at a point which must not be on the boundary. You're going to get a secant (line between two points that doesn't lie totally on the boundary). This must be crossed to reach all points. Why? After traversing this secant, there are a nonzero number of points on either side. If you go to one side immediately after, you must eventually go to the other. Since you can only travel in straigh lines between extreme points, you must cross the secant. This secant cannot be crossed at an extreme point by 3.

6) Therefore we have: $(...),Px,Q,Py,(...),Pz,Q,Pw,(...)$, where $Q$ is a point that is not on the boundary, where $Py\neq Pz$. Therefore $Px,Q,Py$ and $Pz,Q,Pw$ are lines but are not colinear.

7) This path can be modified in a way that must be the same length obviously: We change to $(...),Px,Q,Pz,(\text{REVERSE}),Py,Q,Pw,(...)$.

8) However since $Px,Q,Py$ and $Pz,Q,Pw$ are non colinear lines, this path can be shortened to $(...),Px,Pz,(\text{REVERSE}),Py,Pw,(...)$. This path is strictly shorter! Hence by contradiction, you can't get non-cyclic paths.


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.