Optimizing finite-length approximations to space-filling loops

Question

Take a loop in the unit disk D^2, with length l where length is defined as the supremum of the lengths of piecewise linear approximations. What is the smallest r such that every radius-r subdisk of D^2 intersects the loop?

The question can of course be generalized by choosing different spaces to "fill", such as polygons, higher-dimensional balls D^n, various other compact manifolds etc. Having a path with free ends rather than a loop is another possible generalization. However, just the initial form of the question has me stumped. I don't know where to begin.

Note that generalizing the dimension of the "loop" does not yield interesting results, as r can be made arbitrarily small for fixed "length" l.

Answer 1

I guess that the problem you are considering is quite hard.

First, let me point out that the similar problem where one tries to minimize the average (instead of maximal) distance to a connected curve of given length has been studied. It is called the irrigation problem, see for example Mosconi and Tilli's paper "$\Gamma$-convergence for the irrigation problem", J. Convex Anal. 12 (2005), no. 1, p. 145-158.

Note that one can twist the problem in several ways: insisting to have a loop is different from considering any curve (possibly branching: in Mosconi and Tilli a curve is simply a Hausdorff one-dimensional compact set, and its length is its one-dimensional Hausdorff measure). In the case of a curve, I would guess that the optimizing shapes are asymptotically the same for the average distance and the maximal distance, that is to say the $1$-skeleton of an hexagonal tilling.

In both cases, one can give at least an estimation of $r$.

First, one can easily get an upper bound by constructing an explicit curve; for example, a loop that is mostly made of vertical lines at distance $2r$ one to each other. It as length of the order of $1/r$, so that you get the estimation $r\leqslant a/l$ for some constant $a$.

One also gets a lower bound by the following argument: consider a square inside your disk of roughly the same size, and divide it into subsquares of side length $3r$. Then a curve that achieve the bound $r$ must go far inside each of these cubes, and have length at least $r$ times the number of edges of a spanning tree of the incidence graph of the cube subdivision. There are roughly $r^{-2}$ vertices in this graph, thus roughly $r^{-2}$ edges in a spanning tree. It follows that you get the inequality $r\geqslant b/l$ for some constant $b$.

The problem is to get precise values for $a$ and $b$; the above strategy can give explicit values, but even with a little bit of optimization it should be difficult to have $a$ close to $b$, though $r(l)$ should be equivalent to some $c/l$.