How many cells can a planar curve touch?

The following question was posted in Yao class WeChat group:

How many cells can a planar curve of length $L$ touch at most?

Here, a planar curve is a continuous function f:[0,1]→R2. Its length is at most L, if all its finite-piece inscribed polylines have length at most L. Formally, this means for all $n\in \mathbb{N}$ and all 0=t0​≤t1​≤⋯≤tn​=1, it holds that $$\sum _{i=1}^n|\mathbf{f}(t_i)-\mathbf{f}(t_{i-1})|\le L.$$ The number of cells $\mathbf{f}$ touches is $$\left|\left\{(x,y)\in {\mathbb{Z}}^2:\mathbf{f}([0,1])\cap ([x,x+1]\times [y,y+1])\ne \varnothing \right\}\right|\stackrel{\text{def}}{==}N.$$

It is evident that N=O(L). The simplest proof is to consider how much length is required to touch 7 cells — strictly greater than one, which implies N≤6L+6. Some fiddling on the scratch paper suggests that the optimum is to walk diagonally with occasional segments parallel to the axes at the ends. This strategy shows that a curve of length $\sqrt{2}n+2$ can touch $3n+8$ cells. How do you prove this (sloppy constants are fine, but sloppy slopes are not)?

The following proof is a collaboration among Yao class alumni. Attribution is given at the corresponding step. This was also posted on Math StackExchange, though we solved it before others gave an answer. The problem was brought up by Zishuo Zhao. Hard-to-count many alumni took part in the discussion.

Looking at the Dual

It suffices to consider the following dual problem, put forward by Lunjia Hu:

Select $N$ cells. For each of them, select one point from one of its four edges. Connect them in some order. What is the minimum length of the polyline?

It is routine to see the following real dual is equivalent to the primal:

Select $N$ cells. What is the minimum of the length of a curve passing through all those cells?

Now we show the real dual can be confined to the aforementioned dual.

In the figures, the blue/red/greenpurple/red/blueyellow/teal/greenblue/teal/green represents auxiliary vertices and before/after adjustments in the proofs.

Proof. Let the cells that $\mathbf{f}$ touches be $B_i=[x_i,x_i+1]\times [y_i,y_i+1]$ for $x_i,y_i\in \mathbb{Z}$ and i=1,…,N. Consider the ‘first time each cell is touched’. Formally, let $$t_i=\inf \left\{t\in [0,1]:\mathbf{f}(t)\in B_i\right\}.$$ Since the curve touches each cell, each $t_i$ is well-defined. Using the continuity of $\mathbf{f}$ and the compactness of Bi​, it is routine to show those infima are in fact minima. Also, if ti​​=0, it must be the case that $\mathbf{f}(t_i)$ is on a grid-line. Assuming WLoG that $t_i$ is sorted in increasing order, we see that the polyline connecting $\mathbf{f}(t_1),\mathbf{f}(t_2),\dots ,\mathbf{f}(t_N)$ still touches all the cells and is not longer than f. This almost finishes the transform, except that the point on the first cell might not be on a grid-line. This can be solved using the same argument again, but choosing the last point of each cell that the current polyline touches.

Note that we formulated the dual problem as a minimum, not just an infimum. We know certain $N$ cells can be touched using a curve of length, say, N. By translation invariance, the real dual can be confined to the case where all the cells are inside the ball centered at the origin of radius N+1. We can thus enumerate which cells to use, in what order. Once that is fixed, the optimization involves choosing $2N$ numbers from $[0,1{]}^{2N}$ and optimising a continuous function. Overall, the dual can be written as the minimum of many many continuous functions, which itself is continuous, hence admits a minimum over the compact set [0,1]2N. The fact that there is a minimum is the most useful fruit of looking at the dual problem.

Necessary Conditions for Minima

We now find some necessary conditions for the minima. First, we consider all the vertices (the ‘internal’ vertices) except the first/last ones. Let the two ‘arms’ at an internal vertex be the two segments connecting to this vertex. We also confine the arms to be within one cell (take the ‘prefix’ closest to the vertex in question).

Claim. For any minimum, the internal vertices must be in one of the following cases:

1. It is a lattice point (having integer coordinates).
2. Its two arms share the same slope — this is a ‘straight’ point.
3. Its two arms have opposite slopes — the polyline ‘reflects’ at this point.

Proof. If it is not a lattice point, it must be in the internal of a grid-segment (an edge of a cell). Suppose the two arms do not share the same slope. If its two arms were in different cells, we could connect the other ends of the arms to shorten the length. Therefore, its two arms must be in the same cell. If the two arms did not have opposite slopes, we could move the vertex until its two arms does so, which would again shorten the length. This completes the proof.

‘Newly Touched Cells’

We now switch back to the primal problem, this time with the restriction that the curve satisfies the previously discussed conditions.

For any curve, let the number of ‘newly touched cells’ be the number of cells it touches minus the number of cells its starting point touches. Clearly, the number of newly touched cells is subadditive under concatenation, additive under concatenation of two segments chopped from a single segment, and this function is invariant under reflection around any grid-line. It also upper-bounds the objective (by a constant additive term of 4). Lunjia Hu and Zhiyi Huang pointed out these convenient properties of this function, which allows us to eliminate the third situation from the internal vertices as follows:

1. Cut the polyline into slices at lattice points.
2. For each slice, cut it into segments at reflection points, reflect the segments appropriately and reassemble them into a segment.
3. Reassemble the slices.

This process yields a solution with a larger sum of newly touched cells of segments, and the internal vertices of the polyline are not in case 3. (Use subadditivity and additivity.)

Last Steps

The rest are the simplest steps (and done by me, the weakest chicken [最弱鸡的😂]).

Consider a segment whose two ends are lattice points and which do not touch any other lattice point internally. It is routine to show that the offset of coordinates are coprime integers p,q. A simple counting shows that the efficiency (number of newly touched cells over length) of this segment is $$\frac{p+q+1}{\sqrt{p^2+q^2}}\le \frac{3}{\sqrt{2}}.$$

For the first/last segments (mind you, they might be the same segment!), they might not have lattice point ends. However, since we cut the segments at lattice points when doing this final counting, it also does not have internal lattice points. This means it touches at most, say, $p+q+16$ cells, where $p,q$ are the coordinate offsets. If p2+q2≥162⋅2, the efficiency is p2+q2​p+q+16​≤2​3​. Otherwise, we have p+q≤32. This means either the efficiency is small, or the absolute number of cells touched is small.

Lastly, the cells the starting point touches is at most 4. Combining all these, we get $$N\le \frac{3}{\sqrt{2}}L+100.$$ Here, 100=(32+16)×2+4. With more care one might obtain a tighter bound. Ideally one can prove the starting/ending points are also integral, but I am satisfied with this.

Bonus Chatter. This proves, albeit tediously, that rectifiable curves (those of finite length) have box-counting dimension 1. In fact, this is a low-resolution box-counting bound. I happened to have watched a very nice video about box-counting dimension by 3Blue1Brown.