TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Tuesday, February 05, 2019

Number of Neighbors in a Tiling





Part A of the picture shows a tiling of the plane with identical rectangles such that each rectangle has 6 neighbors (a unit tile can be the neighbor to another only if they share some some finite portion of the boundary - corner to corner touch is not counted as neighborness). Obviously, in a corner to corner layout with the same rectangles, each unit has only 4 neighbors. With hexagonal units, each tile can have six neighbors at the most.

As shown in Part B of the picture, one can have tilings where some units can have many neighbors (like the yellow one) but then some others have considerably fewer (as for the red one). So, the average number of neighbors per tile over the entire plane remains low.

Basic Question: Are there tiles such that for *some* tiling of the plane with copies of it, the number of neighbors averaged over all tiles is more than 6? The unit tile may be non-convex, anything. So the question is whether 6 is such a strict upper bound for the *average* number of neighbors a tile can have. If not, how high can it go?

Answer: See this page for example:
http://www-math.mit.edu/~djk/18.310/18.310F04/planarity_coloring.html
By a smart application of Euler's formula, we do have the result: "a planar graph on v vertices can have at most 3v-6 edges and average degree strictly less than 6". And under the constraints given above, the graph with tiles as nodes and neighborness as edges is a planar graph. And even if we consider non-convex tiles, this bound appears to hold.
In 2D, if we consider any packing but non tiling arrangement with infinitely many copies of a given unit (ie, there could be gaps in the layout as there will be in the case of say, regular pentagons), even then, the neighborness relation leads to a planar graph. So the basic bound above remains unaltered.

Extension: If a corner-to-corner contact between two tiles is sufficient for their being taken as neighbors, then the upper bound of the average number of neighbors over all tiles seems to be 12 (as happens with triangular tiles). In this case, the neighborness graph is no longer planar as can easily be seen.

Note 1: One can worry about higher dimensions for both the basic question and the extension (in 3D, neighborness between units could be of 3 types - face to face, along an edge or contact at just one point).

Note 2: In 3D, we could also ask if there is an upper bound to the number of neighbors in rigid (but non-space-filling) packings with copies of any given 3D shape (not necessarily a convex 3D shape).

0 Comments:

Post a Comment

<< Home