Convex polygonal tiling of the square such that every line intersects at most k polygons

Question

Consider a tiling of a square by convex polygons, such that every line through the square intersects at most $k$ polygons. Let $n$ be maximum number of polygons such a tiling can have. What is the dependence of $n$ on $k$?

Tiling the square with a grid of $k/2$ by $k/2$ smaller squares gives a simple construction for $\Omega (k^2)$ polygons. But is $n \in O(k^2)$?

If each polygon has the same area $A$, the answer is yes. The sum of the horizontal lengths of the polygons cannot exceed $k$, otherwise some vertical line will intersect more than $k$ polygons by pigeonhole. The same follows for the vertical lengths of the polygons. Let $L_i$ be the sum of the horizontal and vertical lengths of polygon $i$, then $L_i \geq 2\sqrt{A}$. We have $n = \frac{1}{A}$ and $\Sigma_i L_i \leq 2k$ so $$2n\sqrt{A} \leq 2k$$ $$\sqrt{n} \leq k$$ $$n \leq k^2$$

This proof only makes use of vertical and horizontal lines intersecting at most $k$ polygons. If a general upper bound exists, the proof must make use of diagonal lines intersecting at most $k$ polygons as well: an arbitrary number of arbitrarily small squares could be placed along a diagonal line, with two large polygons filling the space above and below the line, and in this tiling vertical and horizontal lines would only intersect a small constant number of polygons.

Any suggestions or references would be greatly appreciated.

Answer 1

It seems that there is no upper polynomial bound, even for the rectangular tilings.

Choose a large $d$. Start with a $d\times d$ rectangular partition; make the sides of rectangles different. You may make this in a manner that you may choose $d$ vertices of these rectangles such that (i) they are in a general position and lie in the interior of the square, and (ii) no two are vertices of the same rectangle of partition.

Now, for every chosen vertex, perform the following operation. `Skew' the four rectangles sharing this vertex as shown in the Figure below, and partition $A$ into $d\times d$ rectangles again.

This way, you obtain about $d^3$ rectangles, but each line crosses $O(d)$ of them (since it crosses at most two `insertions').

Iterating such procedure, you may obtain the number of rectangles greater than an arbitrary power of $d$, but each line will still cross $O(d)$ rectangles.

[ADDENDUM] Here is another procedure, working for general partitions.

Start with any partition of the square where the vertices are in a general position. At each step, we replace each interior vertex (adjacent, say, to $e$ edges) with a very small $e$-gon. We may do this preserving the condition that all the vertices are in general position.

At each step, the maximal number of crossings increases by at most 2 (if the new polygons are small enough). On the other hand, the number of vertices grows exponentially, thus so does the number of polygons.

Answer 2

The correct upper bound seems to be of order $k^k$ in the sense that we can create $\ge k^k$ polygons so that each line intersects at most $Ck$ of them and the number is bounded from above by $k^{Ck}$. I'll prove the second part of this claim here.

Definition. Let $A,B$ be two closed convex polygons with disjoint interiors. We say that a finite sequence of closed convex polygons with disjoint interiors also disjoint from the interiors of $A$ and $B$ is a chain connecting $A$ to $B$ if the first polygon has a common point with $A$, each other polygon has a common point with the previous one, and the last polygon has a common point with $B$.

Lemma. Suppose that $\mathcal F$ is a family of chains of length at most $L$ connecting $A$ to $B$. Suppose that no line intersects more than $k$ different polygons forming these chains. Then $|\mathcal F|\le (kL)^L$.

Viewing the original tiling as a sequence of chains connecting the left side to the right one of length at most $k$ (say, the chains of polygons crossing a fixed horizontal line), we get the upper bound $k^{2k+1}$ in the original problem.

Proof. Induction on $L$. If $L=0$, there is nothing to prove (there is only one empty chain). Case $L=1$ is also trivial because each chain consists of exactly one polygon that has to cross any line that separates the interiors of $A$ and $B$.

To make an induction step, let us first estimate the number of chains containing a fixed polygon $C$. Notice that for each such chain we can find two numbers $a,b\ge 0$ with $a+b=L-1$ such that our chain (of length $\le L$) consists of a chain of length $\le a$ connecting $A$ to $C$, then $C$ itself, and then a chain of length $\le b$ connecting $C$ to $B$. By the induction assumption, the total number of chains containing $C$ is then at most $$ \sum_{a+b=L-1}(ka)^a(kb)^b=k^{L-1}\sum_{a+b=L-1}a^ab^b\le k^{L-1}L^L $$ Now notice that each chain crosses any line separating the interiors of $A$ and $B$, so at least one polygon in it crosses that line. However, each particular polygon can be found in only $k^{L-1}L^L$ chains, so, unless the line crosses more than $k$ different polygons, we may have only $k\times k^{L-1}L^L=(kL)^L$ chains.

Of course, this upper bound can be improved a bit, but, as I said, not by too much.

Edit. I guess I simplified my original construction enough to make it postable, so here goes.

The starting point is a very long horizontal rectangle $R$ of height $1$ split by $k$ extremely narrow diagonal (angle of 45 degrees with the horizontal axis) paralellograms placed into it at regular (also very long) intervals in the middle half (so we have $2k+1$ pieces in the original picture).

At every step, we shrink the picture we already have enormously in the vertical direction, scale it so that it gets width $2$ (something between $\sqrt 2$ and $2\sqrt 2$), rotate it by 45 degrees, place $k$ copies of it the way the narrow parallelograms were placed in the starting picture with some smalll shifts so that no 3 "narrow parallelograms" in different copies are crossing one line (which is possible because those look like points now), and cut out the pieces hanging outside $R$ (see the picture with $k=3$). We do this $k$ times.

The main property of this picture is that if we have a line that is almost vertical (say, making the angle of 10 degrees or less with the vertical axis), then it intersects at most 2 big pieces in the top generation and at most one picture in the next generation. Moreover, any line that violates the last property should be nearly horizontal, which means that with respect to the picture of the previous generation it is nearly vertical after we undo the enormous compression in the vertical direction, but being nearly vertical there, it stays nearly vertical for all following generations as well after the corresponding decompressions.

Suppose we have any line now. Let's see how it goes across the pictures from the top generation down. For a while it intersects just $\le 2$ pieces in the current generation and at most one picture in the next one. This sort of intersections is harmless because we get 2 pieces per generation only. At some generation $g$ this nice property may get violated. Then the line must be nearly hzontal in the decompressed picture for $g$, so it can cross $\le k+1$ big pieces from generation $g$, $\le 2k$ big pieces from generation $g+1$ and at most $2$ pictures from generation $g+2$. Moreover, it stays nearly vertical for all generations starting with $g+1$, so we return to the rate of 2 pieces per generation (well, it is $4$ now because we crossed $2$ pictures in generation $g+2$, but it is still harmless). So the total number of crossed pieces is still under $Ck$ while we clearly have at least $k^k$ pieces total.