# Does dividing the unit square into small enough polygonal regions always yield a region surrounded by at least six others?

Divide* the unit square $$I^{2}=[0,1]\times[0,1]$$ into polygonal regions, each having the property that the distance between any two of its points is less than $$\frac{1}{30}$$.

Question: Must there be a polygon $$P$$ within $$I^{2}$$ surrounded by at least six adjacent polygons- that is, touching $$P$$ in at least a point? If yes, how to prove it?

*The polygons in the division may not be convex and the division may have "gaps" in the sense that the boundary between two adjacent polygons may be a disconnected polygonal line. The picture below illustrates gaps (white polygons) between the two grey polygons $$P$$ and $$P'$$.

$$\hskip2.25in$$

For example, the division pictured below has gaps.

$$\hskip2in$$

I think the answer may be yes from some drawings. And I do not think it matters if there are gaps. Indeed, these gaps will be produced by polygons in the original division. We can merge them with adjacent polygons in order to produce larger polygons and yield a new division of $$I^{2}$$ such that any two adjacent polygonal regions have either a point or a connected polygonal line as boundary between them. Since this process only decreases the number of adjacent polygons a polygon has then if the answer is affirmative for this new division, then it must also be affirmative for the original division. But that is as far as I have been able to go towards a solution.

• I don't get the part about gaps. Surely you're required to fill the whole square?
– Karl
Jan 31 at 14:56
• If gaps are allowed the answer is clearly no. You can surround each polygon with a gap and none of them touch at all. Jan 31 at 15:04
• Yes, certainly we are required to fill the entire square. I clarified what I meant by gaps.
– John
Jan 31 at 15:42
• I'm not sure if it helps, but if a counterexample exists then a counterexample exists where no corners touch each other. You can always "bulge" where two corners touch such that the number of number of regions a region is touching is either constant or decreases. Jan 31 at 18:11
• This is very interesting. Adding on to QC_QAOA, and not allowing gaps, you may as well consider simply connected regions. Then it’s a question of topology. Jan 31 at 21:31

Yes! That is, assuming no gaps.

Form a connected path along the boundaries of regions from one side of the square to the opposite side. Now, consider the boundaries of all the regions touching the path. You get two bands of regions. Repeat to get three adjacent bands. If there were at most 5 adjacent regions, each region in the middle band must either touch only one region in the lower band or only one region in the upper band. Moreover, each region in the lower and upper bands can touch at most two regions in the middle band. So, we get a leapfrog pattern like the one shown. Then, you have a regions in the upper and lower bands touching 3 regions in the middle band, two in their own band and at least one more outside any of the three bands.

• You need 4 bands and at least 3 regions in a middle band. So if the max diameter of a region is, say 0.25, it should be enough. Jan 31 at 23:03
• As long as the max diameter is no more than 0.25, my argument should work. And, $1/30<0.25$ Feb 1 at 4:26
• I agree with your argument but disagree with your assessment that $.25$ works as a diameter bound (for your argument). I would say that as written you would require at least $5$ regions across and at least $5$ bands so any diameter less than $.2$ would work (and $\frac{1}{30}<\frac{1}{5}$). It's an interesting question on what the supremum of such a bound is. Clearly its less than $\frac{\sqrt{2}}{2}$ but I wouldn't know how to make that any smaller. Feb 1 at 13:36
• @QC_QAOA You're right. Heres such an example with 4 bands and 3 across. That means the max diameter should not exceed $\sqrt{1/4^2+1/3^2}=5/12$ . I've included a pic. Feb 1 at 17:51

First, let us consider the case in which our division $$D$$ of the square has no gaps. That is, the boundary between any two polygons of $$D$$ is either a point or a connected polygonal line.

Consider the polygon $$P_{0}$$ containing the center $$O$$ of the square ($$O$$ may lie on a boundary, in which case we select any of the polygons sharing that boundary). Note that $$P_{0}$$ lies inside a circle of radius $$\frac{1}{10}$$ centered at $$O$$. We say that $$P_{0}$$ is a polygon of type 1.

Now, notice that all the polygons adjacent to $$P_{0}$$ are inside a circle of radius $$\frac{2}{10}$$ centered at $$O$$. We call these polygons of type 2. Continuing, all the polygons adjacent to a polygon of type 2 will be called polygons of type 3, and all the polygons adjacent to a polygon of type 3 will be called of type 4, and so on.

We observe the following properties of classifying polygons by type:

1. Polygons of type 5 always exist. Indeed, it is clear that $$P_{0}$$ and all the polygons of types 2, 3 and 4 are contained inside a circle of radius $$\frac{4}{10}$$. Hence, polygons of the first four types never touch the boundary of the square and we will always need to have polygons of type 5 in order for our division to fill-up the square.
2. For $$n\ge2$$, every polygon of type $$n$$ has at least one adjacent polygon of type $$n-1$$.
3. If a polygon $$P$$ has type $$n\geq 1$$, then no adjacent polygon can have type $$n-1$$, for otherwise $$P$$ itself would have type $$n-1$$. Hence, any two adjacent polygons must have either the same type or types differing by one.
4. If a polygon $$P$$ of type $$n\geq 2$$ has less than two adjacent polygons of type $$n$$, then it has no adjacent polygons of type $$n+1$$. Indeed, for otherwise $$P$$ would share part of its boundary with a polygon of type $$n+1$$, and share another part of its boundary with a polygon of type $$n-1$$ (by Property 2). In lieu of violating Property 3, these two polygons could not touch. Therefore, there would be at least two regions where $$P$$ lies in contact with polygons of type $$n$$, other types prohibited by Property 3. But we are in the case that two adjacent polygons touch only along a connected polygonal segment (or a point), hence, $$P$$ is necessarily adjacent to at least two distinct polygons of type $$n$$.

The idea now is to assume that every polygon is surrounded by at most five polygons and conclude that no polygon of type 4 can be adjacent to polygons of type 5, i.e. there are no polygons of type 5, which is a contradiction by Property 1. Indded, for a polygon $$P$$ of type 4 we consider two cases:

If $$P$$ is adjacent to at most one polygon of type 4, then by Property 4 it clearly cannot be adjacent to a polygon of type 5.

Suppose that $$P$$ is adjacent to at least two polygons of type 4. First, $$P$$ will be adjacent to at least two polygons of type 3. Indeed, suppose not and let $$P'$$ be the only polygon of type 3 adjacent to $$P$$. Then $$P'$$ is adjacent to at least two polygons of type 4, apart from $$P$$- namely, the two polygons $$Q$$ and $$Q'$$ which border $$P$$ at the ends of its common boundary with $$P'$$ (see picture below)

$$\hskip2.5in$$

$$Q$$ and $$Q'$$ cannot be of type 3 since we assumed $$P$$ is adjacent to only one polygon of type 3 (the polygon $$P'$$), and they cannot be of type 5 by Property 3. Furthermore, $$P'$$ is adjacent to at least two polygons of type 3 (by Property 4) and to at least one polygon of type 2 (by Property 2), a total of six polygons, which is contrary to our hypothesis. Hence, $$P$$ is adjacent to at least two polygons of type 3, as desired.

Next, we will show that $$P$$ is adjacent to at least three polygons of type 3: If $$P'$$ is any polygon of type 3 adjacent to $$P$$ (we know there are at least two of these) it will not have adjacent polygons of type 4 apart from $$P$$. Indeed, by property 4, $$P'$$ is adjacent to at least two polygons of type 3. Moreover, it is adjacent to at least two polygons of type 2 (which can be proved in exactly the same way we proved that $$P$$ was adjacent to at least two polygons of type 3). However, since by hypothesis $$P$$ is adjacent to at most five polygons, $$P$$ must be the only polygon of type $$4$$ adjacent to $$P'$$. Now, let $$Q$$ and $$Q'$$ be the polygons touching $$P$$ at the ends of the boundary it shares with $$P'$$. These must be of type 3 and adjacent to $$P$$. Therefore, $$P$$ is adjacent to at least three polygons $$P'$$, $$Q$$, and $$Q'$$ of type 3, as desired.

Finally, notice that $$P$$ cannot be adjacent to polygons of type 5, for otherwise it would be adjacent to at least two polygons of type 4 (by Property 4), at least three polygons of type 3 (as we have just seen), which makes up at total of at least six, contrary to our hypothesis. The result is proven.

What happens when our original division $$D$$ has gaps? Well, as it was explained a little in the question, if two polygons $$P$$ and $$P'$$ of $$D$$ have gaps then the boundary they share is disconnected and these gaps are made up of polygons in our division (see the first picture in the question). We will produce a new division as follows: Add to $$P$$ all the gaps between it and its adjacent polygons in order to obtain a larger polygon $$P_{1}$$. Then do the same with all the adjacent polygons of $$P_{1}$$, and so on. The new division $$D'$$ thus formed has the property that the boundary shared by any two polygons is either a point or a connected polygonal line. Moreover, this process only decreases the number of polygons adjacent to a polygon. Hence, if some polygon of $$D'$$ is adjacent to at least six polygons, the same must have been true of the original division $$D$$. Note that each polygon $$P'$$ of $$D'$$ is contained within a polygon $$Q$$ obtained by adding to $$P$$ all the polygons adjacent to it and all the gaps between it and the polygons adjacent to it. Since by hypothesis both $$P$$ and all the polygons adjacent to it have diameter at most $$\frac{1}{30}$$, $$Q$$ has diameter at most $$\frac{3}{10}=\frac{1}{10}$$ (see picture, where the diameter of $$Q$$ is depicted via red lines, each of which must have length $$\leq\frac{1}{30}$$) and $$P'$$ has diameter no greater, which is what we want.

$$\hskip2in$$