Proof: No Polygon Tiling by Convex Quadrilaterals | Geometry Statement

[0rthodontist]

I have devised the following statement and a short proof of it:
No polygon may be tiled by convex quadrilaterals, each of which shares exactly one face with the polygon.

Is this known or trivial, or where could I find out if it is?

 

[DaveC426913]

Not that I doubt you, but are there any further conditions that you are assuming, such as
-no convex polygon
-a single convex quadrilateral

As it stands, your polygon could be any shape (such as a star), and you could use any or many of an infinite range of shapes and sizes of quadrilaterals to tile.

 

[0rthodontist]

The polygon does not have to be convex and since each quadrilateral shares a side with the polygon, there will be as many quadrilaterals as the polygon has sides. There is no restriction on the shapes or sizes of the quadrilaterals, other than that they must be convex.

 

[Office_Shredder]

EDIT: Never mind, I missed the word "convex"

 

[0rthodontist]

One thing that is not clear is whether this is also true if you use convex n-gons for n > 4 instead of quadrilaterals. I would suspect that it is.

 

[DaveC426913]

"...since each quadrilateral shares a side with the polygon, ..."

My bad. I misread your post. I thought it said a MAXIMUM of one face (as in, you could have entirely internal quads that share zero faces). In fact it says EXACTLY one face. So, point retracted.


Further clarification, though this may be bifurcating bunnies: I'm not sure the wording makes it clear that a quad shares the ENTIRE face of the polyogn, i.e. does it exclude two or more quads sharing the same polygonal face?

 

[0rthodontist]

I'm not sure the wording makes it clear that a quad shares the ENTIRE face of the polyogn, i.e. does it exclude two or more quads sharing the same polygonal face?

The way I intended it, it does, but it doesn't make much difference since you could easily turn a polygon tiled multiple-to-a-face (if one existed) to a polygon tiled one-to-a-face by adding vertices between the quadrilaterals on the polygon faces, and making the polygon faces bend back and forth at those vertices to differentiate them.


The reason I'm posting this here is not just to discuss the problem, but to ask what I can do with this now that I have it. Is it trivial by some theory--where should I go to find that out--and if it doesn't seem to be trivial is there a next step? Find a professor? Could I possibly get it published? My proof is centered around a graphical case analysis that, while I believe is sufficient, I don't know how to make much more rigorous/algebraic.

 

[0rthodontist]

Well, what kind of math is this? I have a feeling it's not really "geometry" in the modern meaning. It's euclidean geometry--who is most likely to be familiar with this? If I am looking for a professor, what kind of professor should I look for?

 

[0rthodontist]

Well, I emailed a professor and I'm waiting for his response. Anyway, this is my proof.



I will refer to these diagrams:

http://img150.imageshack.us/img150/8420/quadriprd5.png

In the diagrams, I use the following notation:

Curved, dashed lines indicate an unknown number of sides (at least one)

Straight, solid line segments indicate a single side

Blue indicates the exterior of the polygon. This means that any tiling quadrilateral must share one face with it.

Red indicates line segments on the interior of the polygon that have no restriction in the number of sides where a quadrilateral may contact them.

Green indicates a tiling quadrilateral. Notice that for the purpose of placing an additional tile, green functions the same as red--I only use the additional color red for clarity.

Small black circles indicate a part of a line segment which must be covered by another quadrilateral tile, with subsequent diagrams listing the possible ways in which it may be covered.


The central aim of this proof concerns four kinds of regions, which I call q, t, f, and b. f, for "flat," consists of a red segment whose endpoints are joined by a blue dashed line (part of the polygon exterior) as in 1a. t, for "tri," consists of two red segments that form a angle that is less than a flat angle, together with part of the polygon exterior, as in 2a. b, for "bent," is the same as t except the red segments form a reflex angle, as in 1.2a. q, for "quad," consists of three red segments, one pair of which forms an ordinary non-reflex angle and the other pair of which forms a reflex angle, with the ends joined by part of the polygon exterior, as in 3a. I will show that tiling anyone of these regions requires one to tile one of the other three regions.

Let n(L) denote the minimum number of quadrilaterals (alternatively, the minimum number of sides represented by the blue curved dashed line) which can tile region L, where L = q, t, f, or b. If, for example, a minimum tiling (... by quadrilaterals, where each shares exactly one edge--this will be implicit for the rest of the proof) of q contains within it a tiling of t, we must have n(q) > n(t). Note that a minimum tiling cannot contain within it another tiling of itself. I will show:
1. n(f) exists --> n(f) > n(q) or n(f) > n(t) or n(f) > n(b)
2. n(q) exists --> n(q) > n(b) or n(q) > n(f) or n(q) > n(t)
3. n(t) exists --> n(t) > n(q) or n(t) > n(f)
4. n(b) exists --> n(b) > n(q) or n(b) > n(f) or n(b) > n(t)
These are summarized in the box in the diagram titled "Structure," with an arrow from x to y if one of the ways to tile x contains a tiling of y, where every way of tiling x is represented by some arrow on the graph. A minimal tiling of some region consists of a path in the graph moving from tiling to sub-tiling, with no vertex repeated--if a vertex were repeated it would amount to the minimal tiling containing itself, which is impossible. But since the graph has only 4 elements some vertex must repeat, so if the relationships given above hold, none of the regions can be tiled.


In the following, I will use the "left" side of a quadrilateral to mean the side clockwise from the side contacting the polygon, the "right" side of a quadrilateral to mean the side counter-clockwise from the side contacting the polygon, and the "top" side of a quadrilateral to mean the side opposite from the side contacting the polygon.

First examine f. In 1a, the circled part of the line segment consists of the vertex and a small portion of the red segment. With some thought you can see that any tiling of f must contain a quadrilateral that shares that vertex and also has an edge that coincides with some part of the red line segment to the left of that vertex--this is one of the areas where the proof could be made more rigorous but it is clearly true. Now examine the possible ways in which the quadrilateral could cover the circled part:
b. It could be covered by the right side of the quadrilateral. This requires one to tile a region of type q (or another region of type f; see Note 1, explained below)
c. It could be covered by the top of the quadrilateral. This requires another tiling of f (so it can be immediately rejected).
d. It could be covered by the left side of the quadrilateral. This requires a tiling of type b.
By design, b, c, and d exhaust all possible placements of the quadrilateral that covers the circled part of the red line segment.


Note 1: If a quadrilateral contacts the blue again with a corner of its top side, it requires another tiling of type f. This will be used implicitly throughout the proof to reduce the number of diagrams drawn.


Now examine t. The circled spot in 2a again consists of the vertex and a small amount of line segment, and it must be covered by some quadrilateral. The options are:
b. The quadrilateral covers it with its top side. This leaves another tiling of type t.
c. Right side, where the top side does contact the left red segment. This requires a tiling of type t.
d. Right side, where the top side does not contact the left red segment. Type q. (Note 1 is used here and in part c)

Now examine q. The circled spot in 3a consists of the vertex and a small amount of line segment to the right of the vertex. The options for covering this are:
b. Cover it with the top of the quadrilateral, where the right top vertex of the quadrilateral does not reach to the other red vertex. Type q.
c. Use the top of the quadrilateral, where the right top vertex reaches exactly to the other red vertex, and the angle formed by the right side of the quadrilateral and the rightmost red line segment is less than flat. Type t.
d. Use the same situation as before, only the angle mentioned is flat. Type f
e. Use the same situation as before, only the angle mentioned is reflex. Type b.
f. Use the top of the quadrilateral, where the right top vertex reaches past the second red vertex. Type q. Note 1 is used here.
g. Use the right side of the quadrilateral. Type t.

Now examine region b, a more complicated situation. The black circle in 4a includes the central vertex and a small amount of line segment to the right of it. The possibilities are:
b. Use the top of the quadrilateral. Type t. (Use of Note 1)
c. Use the left side of the quadrilateral. Type q. (Use of Note 1)
d. Use the right side of the quadrilateral, where the right side does not extend any farther than the red vertex. Type q (Use of Note 1)
e. The final option is to use the right side of the quadrilateral, where the right side reaches beyond the red vertex. Note 1 is used for the top left vertex, and if the top right vertex contacted the blue, it would form a region of type t. This is a more complex example. The circled area is the green top right vertex and a small part of the right side, and it must be covered by another quadrilateral. Parts f, g, and h are the possibilities for such a covering.
f. Use the right side of the (second) quadrilateral. Type q
g. Use the top side of the quadrilateral, where the top right vertex of the second quadrilateral does not reach beyond the top right vertex of the first quadrilateral. Type q.
h. The last option for this covering is to use the top side of the quadrilateral, where the top right vertex of the first quadrilateral does reach beyond the top right vertex of the first quadrilateral. Note 1 is used. This requires a further covering. The circled place includes the top right vertex of the first quadrilateral and part of the top of the first quadrilateral. The possibilities for this are shown in i, j, and k.
i. Use the right side of the (third) quadrilateral. Type t.
j. Use the top of the quadrilateral, where the left side of the quadrilateral contacts the top of the second quadrilateral. Type t.
k. Use the top of the quadrilateral, where the left side of the quadrilateral does not contact the top of the second quadrilateral. Type q.


So, now, if I have not missed something, I have proven that q, t, f, and b are untilable. To show that any general polygon is untilable, look at 5a. The circled region is some part of the top of the first quadrilateral. Some other quadrilateral must cover some part of the top of the first quadrilateral for there to be a successful tiling. (Note 1 is used in the placement of the first quadrilateral) The possibilities are:
b. Use the top of the second quadrilateral, where the "left top" vertex (in this picture, it is the right bottom vertex, since the quadrilateral is upside down) of the second quadrilateral lies before the right top vertex of the first quadrilateral. This is type q, so it is ruled out since we now know that q is untilable.
c. Use the top of the second quadrilateral, where the left top vertex lies after the right top vertex of the first quadrilateral (Note 1). Type q.
d. Use the top of the second quadrilateral, where the left top vertex of the second quadrilateral and the right top vertex of the first quadrilateral coincide, and the angle formed by the right side of the first quadrilateral and the left side of the second quadrilateral is not a straight angle or a reflex angle. Type t.
e. Use the same situation as before, only the angle is reflex. Type b.
f. Use the same situation, only the angle is straight. Type f.
g. Use the right or left side of the second quadrilateral. Type t.

Since every possible way to place the second quadrilateral leads to an impossible tiling, no polygon may be tiled by quadrilaterals such that each quadrilateral shares exactly one side with the polygon.

 

[0rthodontist]

So is my proof clear? Are there parts that should be more rigorous (other than the black-circled line segment part, which I know about)? Is there a mistake, maybe an omitted case in the diagrams or something else elsewhere?