TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, March 28, 2019

More on 2D Layouts with 'Unique Neighborhoods'

In an earlier post here (https://nandacumar.blogspot.com/2019/01/a-bit-more-on-kissing-numbers.html), I had asked:

---------
In an arrangement of copies of a certain region C, let us define the neighborhood of any single unit, C0 as the set of copies of C kissing C0 plus the relative positions and orientations of these kissing copies. Let residents of two unit C's in the arrangement, C1 and C2, note their respective neighborhoods. If these neighborhoods are different for such every pair {C1, C2}, we say every unit C in the arrangment has a unique neighborhood.

Question: Given any 2D convex shape C, pack (not tile) the plane with a rigid arrangement of identical copies of C such that each unit sees a 'unique neighborhood'. No constraint on the number of neighbors each unit has. C could be a disk or square or... This question goes naturally to 3D.

--------

Prof. Janos Pach has shown me a nice construction that solves the problem for circular disks - to pack the 2D plane rigidly with unit disks such that every disk sees a unique neighborhood such that each disk touches 4 other disks.

Consider the following figure:


There is a red polyline formed with segments of unit length roughly following the X axis but with every segment making a unique angle with the X axis. Likewise, the black polyline with uniquely oriented unit length segments roughly follows Y axis. Now, form infinitely many parallel shifted copies of the both polylines as shown; they fill the plane with rhombuses all of which have all sides of unit length but - vitally, no two rhombuses are congruent. Now, place unit disks centered at each of the vertices of the layout of rhombuses and we have a rigid layout of unit disks with contact number 4 throughout but with every neighborhood unique.

Further insights should come our way on higher dimensions, going from disks to general convex shapes and so forth...

Update (May 9th 2019):

Recording a further question on unique neighborhoods.
Can a tiling of the plane be done with any unit at all (not necessarily a convex unit) such that every tile has a unique neighborbood? Althernatively: A tile plus the tiles that touch it together form a big polygon and every such big polygon in the plane-filling layout should be unique.

Looks tough! Even the spiral layout with two poles using enneagonal tiles (due to Voderberg and given in Fejes Toth's 'Regular Figures') might not meet this requirement....and as usual, the question has obvious higher dimensional analogues.

Note 1: The question of finding a single tile that tiles the plane only aperiodically is known to be a classic problem. I suspect the present question is a more tightly constrained question than that and hence might be easier to answer.

Note 2: One can easily form layouts with the same unit rectangle so that infinitely many different possible neighborhoods are seen in the full layout of tiles - just form infinite rectangular strips 1 unit wide with the rectangles and arrange them side by side with each strip shifted along the length with respect to the previous strip by a unique irrational and small epsilon; this will ensure that no two tiles from two different strips will have the same neighborhood.