Suppose $S\subset\mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to S$ is a continuous curve that passes through every extreme point of $S$, i.e., the convex hull of $\Gamma([0,1])$ is $S$. I am interested in obtaining a lower bound on the length $|\Gamma|$ of $\Gamma$.

I conjecture that $$ |\Gamma| \ge C(S) - \ell $$ where $C(S)$ is the perimeter (circumference) of $S$ and $\ell$ is defined as $$ \ell = \sup\{d(e,e'): e,e'\text{ are extreme points of $S$ and $\overline{ee'}\subset \partial S$} \}. $$ Here, $\overline{ee'}$ is the line segment joining $e$ and $e'$. Intuitively, $\ell$ is the length of the longest straight segment in $\partial S$. I think the shortest path $\Gamma$ with $\mathrm{ConvexHull}(\Gamma([0,1])) =S$ can be formed by traveling along the circumference of $S$ from one vertex of the longest straight edge in $\partial S$ to the other vertex. (Obviously, the direction of this path is the one giving $\mathrm{ConvexHull}(\Gamma([0,1])) =S$).

Is the conjectured bound on $|\Gamma|$ above correct? Can one construct a counterexample?

Motivation I'm trying to come up with a simple proof that Isbell's curve solves a particular instance of Bellman's "Lost in a Forest" problem. See this question on MSE if you want to know more about my motivation, but that background is not at all necessary to understand and solve this problem.

  • $\begingroup$ It depends on what you mean by a curve and by length. Is it a continuous map from the interval [0,1] to the plane, and the length is defined in the usual way? Or the length is just 1-Hausdorff measure of a set? $\endgroup$ – Alexandre Eremenko Dec 19 '13 at 6:45
  • $\begingroup$ @AlexandreEremenko I meant the usual arc length defined by approximating with polygonal paths. But I already have a good answer. Thanks for taking the time to look at my question. $\endgroup$ – Will Nelson Dec 19 '13 at 9:13

Let $n$ be large and glue $n$ rectangles, each with the proportions $1\times n$, together end-to-end by their short edges. Then perturb slightly so that all the vertices are in convex position. The perimeter will be roughly $2n^2+2$ (modulo the perturbation), and the longest boundary edge will have length roughly $n$, so $C(S)-\ell$ will be roughly $2n^2-n+2$. However, there is a curve with length roughly $n^2+n+1$ through all the rectangle vertices, that passes once through each short edge of a rectangle and through one of the two long edges of each rectangle, alternating between the top and bottom long sides. So in this case the shortest curve is shorter than your proposed bound by roughly a factor of two.

On the other hand, $C(S)/2$ is an easy lower bound (which this example shows to be close to tight): the shortest (simple) closed curve through all extreme points (their traveling salesman tour) is known to be the same as the convex hull, and is also known to be at most twice the length of any spanning path (or more strongly of any spanning tree) of the extreme points.

  • $\begingroup$ Thanks. That's exactly what I was looking for but hoping not to find. If I'm not mistaken, the lower bound can be improved to $C(S)-\mathrm{diam}(S)$ or even $C(S)-d(\Gamma(0),\Gamma(1))$ using the same traveling salesman argument you mention. But these estimates are way too low for the theorem I'm trying to prove. In that case, $S$ is a circle along with two other points. When the points are outside the circle, close to it, and on opposite sides of it, these estimates are way too low. Perhaps I'll ask another, more direct question specifically about that case... $\endgroup$ – Will Nelson Dec 19 '13 at 9:09

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.