TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Tuesday, September 24, 2019

On Some Infinite Planar Arrangments with Triangles

Background:
Given a convex region C. One can think of a graph corresponding to any planar arrangement of copies of C - each unit is a node and an edge connects it to another node if the two share some finite length of boundary. Such a graph is necessarily planar. As is well known, the average degree of a planar graph can at most be 6.

Now, given any triangle, one can tile the plane with it: join a pair of the triangle into a parallelogram and form infinite strips with these parallelograms and arrange these strips side by side. While putting two strips together one can slide one length-wise a bit with respect to the other. The graph corresponding to this tiling (with each pair of adjacent strips shifted slightly lengthwise) will have the same degree = 4 for every node. One notes a gap between this 4 and the maximum average degree of a planar graph (6).

Question: Can one have any plane-filling arrangement (not necessarily a tiling) with any triangle where the average degree of the corresponding graph is between 4 and 6?

Note: With squares, it is easy to form a tiling with corresponding graph having degree 6 at every node.

Generalization: Given any convex 2D shape C, not necessarily one that tiles. Assume the arrangement(s) with infinite copies of C that maximizes the average degree of the corresponding graph is known. Are these arrangements also good at achieving max packing density?

0 Comments:

Post a Comment

<< Home