12
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

replacement

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.

$\endgroup$
  • 1
    $\begingroup$ How do you iterate the skew procedure? Don't you run out of fourfold vertices in pretty short order? $\endgroup$ – Steven Stadnicki Aug 24 '16 at 22:29
  • 2
    $\begingroup$ @StevenStadnicki This seems to be so, but you can do another thing: imagine that your square is packed by $3$ vertical bricks. Expand every crack between the bricks and pack it with $3$ horizontal bricks so that the "horizontal cracks" (which are of "point size" now) are in "generic position". Now expand the newly created horizontal cracks and fill them with $3$ vertical bricks so that, again, no new cracks are aligned more than necessary, and so on. After $k$ iterations, you'll get $\ge 2^k$ bricks and no line will intersect more than $6k$ of them if the crack expansions were small. $\endgroup$ – fedja Aug 24 '16 at 23:39
  • $\begingroup$ Also, the exponential growth seems to be the best you can get if the numbers of sides of polygons are bounded though I cannot prove it (note that having $m$ sides bounds the number of neighbors only by $mk$, so, despite my $k^k$ bound becomes trivial in this case, the obvious counting by layers still comes short of what one would expect) $\endgroup$ – fedja Aug 24 '16 at 23:47
  • 1
    $\begingroup$ @StevenStadnicki: After the first iteration, I may choose $d^2$ vertices inside the inserted squares, and so on. $\endgroup$ – Ilya Bogdanov Aug 25 '16 at 10:16
8
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ Why do you say that there is a lower bound of about $k^k$? I believe the constructions suggested so far are each exponential; do you have a construction in mind? $\endgroup$ – Maxwell Allman Aug 25 '16 at 17:11
  • $\begingroup$ @Maxwell Allman Yes, I do. Unfortunately at this moment it is all pictures and I have to check some details yet, so posting it would be quite a headache. I'll see if I can simplify it to something a la Ilya's iterative procedure. $\endgroup$ – fedja Aug 25 '16 at 21:20
  • $\begingroup$ @MaxwellAllman OK, I guess I have it in the iterative way. I still need to throw in a couple of pictures though. Do you know any good picture repository? (no registration of any kind, especially with giving them an e-mail or any other personal data, please) $\endgroup$ – fedja Aug 26 '16 at 0:54
  • $\begingroup$ I usually use tinypic.com $\endgroup$ – Ilya Bogdanov Aug 30 '16 at 10:34
  • $\begingroup$ @IlyaBogdanov Thanks! I posted my example (simplified even more, so just one picture is needed). Hope it is readable. $\endgroup$ – fedja Aug 31 '16 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.