0

Let $\Omega\subset\mathbb{R}^n$ be a bounded connected open set. Given a positive number $R>0$ I want to find -if possible- the minimum number of vertices of a polygonal path joining two arbitrary points $x,y\in \Omega$ s.t. the length of the segments is less than $R$. I'm quite sure it is in some sense related to the diameter of the set $\Omega$ but I don't know how to formalize it.

My first attempt was to use that $\overline{\Omega}$ is compact, and thus we can cover it with balls of radius $R/2$ (centered in each point of $\Omega$) and then extract a finite subcover of $N$ such balls: the number of points should be less or equal than $N+1$. But there's something that bothers me since the balls are note entirely contained in $\Omega$ and thus I cannot join with a straight line two arbitrary points in a given ball...

Oromis
  • 676
  • Maximum or minimum number ? Maximum is infinite because you can go forward/backwards as many times you want... – Jean Marie Nov 23 '17 at 11:58
  • Of course minimum, thanks! – Oromis Nov 23 '17 at 11:59
  • Don't you think that for given $x$ and $y$ this number depends heavily on the maybe spongy nature of $\Omega$? – Christian Blatter Nov 23 '17 at 13:46
  • Now I see it does, like @JohnHughes pointed out, and the argument with the balls does not work, but does this imply I can't find an upper bound for the number of vertices? May be it does not depend only on the diameter but somehow on the eccentricity of $\Omega$'s shape... – Oromis Nov 23 '17 at 13:59

1 Answers1

0

Consider a path in the plane that looks like this:

------------------|
                  |
|-----------------|
|
|-----------------|
                  |
|-----------------|

where the spacing between horizontal lines is $u$, and each line runs from $0$ to $1$ in $x$. Take a neighborhood of this path of radius $u/3$ (i.e., move the center of an open ball of radius $u/3$ along the path, and consider the area the ball sweeps out). Call this $\Omega_u$. For $u < 1/2$, $\Omega_u$ can evidently be covered by, say, 9 balls of radius $3/4$ (simply center them at locations $(a, b)$, where each of $a, b$ is $0, 1/2, 1$). On the other hand, for $u = 1/(2n+1)$, we need at least $2n+1$ paths to get from $(0,0)$ to $(1,1)$, even though your argument (for $R = 1.5$) would suggests that no more than $10$ points should be needed. Since my choice of $n$ (and hence $u$) is arbitrary here, this shows that your proof cannot be correct.

Indeed, in general it'll take at least $2n+1$ polygonal segments to join up $(0,0)$ and $(1,1)$ in $\Omega_n$, which probably means that a bound that's based on the diameter of $\Omega$ and $R$ is impossible, since each of these is independents (more or less) of $n$.

N.B. A path with this shape is said to be boustrophaedonic, "in the manner of the plowing of an ox".

John Hughes
  • 93,729