Let $\mathbf{f}:[0,1]\to\mathbb{R}^2$ be a continuous function and suppose the curve parametrized by $\mathbf{f}$ has finite length $\leq L$, i.e., all finite-piece inscribed polylines have total length $\leq L$. What is the maximum number of cells it can touch? By that, I mean the number $$N=\left|\left\{(x,y)\in\mathbb{Z}^2:\mathbf{f}([0,1])\cap\left([x,x+1]\times[y,y+1]\right)\neq\varnothing\right\}\right|.$$

It is simple to prove $N=\mathcal{O}(L)$, say, $N\leq 6L+6$ by considering how much length is required to reach 7 cells. (Citing a friend, the coefficient can be improved to $1+\sqrt2$.)

Some fiddling on the scratch paper suggests that the optimum strategy is to take diagonals of the cells (except perhaps taking grid-lines at the ends), giving $N\geq\frac{3}{\sqrt2}L-c$ for some constant $c$.

Is the above strategy the optimum? How can we prove $N\leq\frac{3}{\sqrt2}L+c'$ for some constant $c'$? Or even just $N\leq\frac{3}{\sqrt2}L+o(L)$?

Extension. How about higher-dimensional spaces? Is the optimum still taking diagonals of length $\sqrt2$? (Taking diagonals of length $\sqrt{k}>\sqrt2$ is suboptimal.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.