Optimal "maze length" in plane tilings

Question

Among the tesselations of the plane (the tiles employed are a finite number of shapes which are allowed to be translated and rotated at will), which one performs best at the following problem?

1. To compare apples to apples, one first rescales the tesselation so that the average area per tile (a weighted average, according to prevalence of each type of tile in the tesselation) is 1.

2. Draw a large disk $D_R$ of radius $R$, centered on a point on the border between some adjacent tiles (not inside a tile), and remove those tiles that are (partially) outside of the disk. Let $S_R$ be the total length of the edges of the tiles that remain (edges between adjacent tiles don't have to be double-counted).

3. Given a point $x(\theta)=(R\cos(\theta),R\sin(\theta))$ on the boundary of $D_R$, let $d_R(\theta)$ be the (Euclidean) length of the shortest connected path from $x(\theta)$ to the center of $D_R$ that stays outside of the interior of the tiles (i.e. only paths that maneuver along the edges of the tiles are allowed). Let $\overline{d_R}=\frac{1}{2\pi}\int_0^{2\pi} d\theta\,d_R(\theta)$ be the angular average of that distance.

4. The problem is to find the tesselation that minimizes $\lim_{R\to +\infty}\frac{\overline{d_R}}{R}$ or the one that minimizes the ratio $\lim_{R\to +\infty}\frac{S_R}{R^2}$ and more generally, the hybrid problem of minimizing ($\alpha \in \mathbb{R}$ a parameter) $$\lim_{R\to \infty}\frac{(\overline{d_R})^\alpha S_R^{1-\alpha}}{R^{2-\alpha}}.$$

Answer 1

I believe that $\lim_{R\to +\infty}\frac{\overline{d_R}}{R}$ can be made arbitrarily close to $1$.

First, note that if we take a given circular patch of tiles and scale every tile by a constant factor $s$, $\overline{d_R}$ and $R$ both increase by a factor of $s$, so we can ignore the unit-area scaling and take any tiling we like.

Now take a square, and cut it with a very large number of lines at different slopes and offsets. This produces a large but finite number of convex pieces. Now let our tiling be given by copies of this cut-up square arranged in the usual manner.

With enough cuts, a point on the boundary of a patch of this tiling will be able to find a line whose slope is very close to its shortest route to the origin, proceed along that line for the extent of its square, and find a nearby line of similar slope at a square-to-square boundary, so that a vanishing fraction of its path is spent on anything besides efficiently approaching the center.

$\lim_{R\to +\infty}\frac{S_R}{R^2}$ seems harder; my guess is that the regular hexagonal tiling is optimal, because this is the solution to the honeycomb problem in two dimensions, but it may be quite hard to prove. (It wouldn't surprise me if someone had considered this variant of the honeycomb conjecture in the literature, though.)

Answer 2

This answer is meant to quickly point out that the honeycomb does not solve the $\lim_{R\to \infty}S_R/R^2$ optimization.

Start with the honeycomb pattern but, at each of the edges of the hexagons, cut out a small (say equilateral) triangle. The equilateral triangles can be kept arbitrarily small compared to the (newly formed) dodecagons. The resulting tiling has 2/1 triangle-to-dodecagon number ratio, so if the triangle area is kept very close to zero, the dodecagon area is allowed to be boosted to almost 3 (under the rules of the problem as it was layed out, i.e. with the average area of the tiles being 1). All in all the asymptotic $S_R/R^2$ ratio then decreases by a factor of almost $3^{1/2}$ compared to the original Honeycomb pattern. The key take-away message is that the number average for the area of the tiles doesn't make for a good benchmark to set up an interesting problem.

(in our example we could have continued fracturing the small triangles into even smaller pieces of tiny relative size, so that the bigger tiles would be allowed to be become even bigger than 3)