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

New contributor
Gee Law is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Your Answer

Gee Law is a new contributor. Be nice, and check out our Code of Conduct.

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.