Binary tiling: Difference between revisions

Revision as of 18:22, 21 September 2024

Revision as of 18:24, 21 September 2024

Line 5:

[[File:Hyperbolic binary tiling.png|upright=1.2|alt=Binary tiling on Poincare disk|thumb|A binary tiling displayed in the [[Poincaré disk model]] of the [[hyperbolic plane]]. Each side of a tile lies on a [[horocycle]] (shown as circles interior to the model) or a hyperbolic line (shown as arcs of circles perpendicular to the model boundary). These horocycles and lines are all asymptotic to a common [[ideal point]] located at the right side of the Poincaré disk.]]

In [[geometry]], a '''binary tiling''' (sometimes called thea '''Böröczky tiling'''){{r|df}} is a [[tiling of the hyperbolic plane]], resembling a [[quadtree]] over the [[Poincaré half-plane model]] of the hyperbolic plane. The tiles are congruent, each adjoining five others. They may be convex [[pentagon]]s, or non-convex shapes with four sides, alternatingly line segments and [[horocycle|horocyclic]] arcs, meeting at four right angles.

There are uncountably many distinct binary tilings for a given shape of tile. They are all weakly [[aperiodic tiling|aperiodic]], meaning that they can have a one-dimensional [[symmetry group]] but not a two-dimensional family of symmetries. There exist binary tilings with tiles of arbitrarily small area.

Line 12:

==Tiles==

In one version of the tiling, each tile is a subset of the hyperbolic plane that lies between two hyperbolic lines and two [[horocycle]]s that are all asymptotic to the same [[ideal point]], with the horocycles at distance <math>\log 2</math> from each other. The resulting shape has four right angles, like a rectangle, with its sides alternating between segments of hyperbolic lines and arcs of horocycles. The choice of <math>\log 2</math> as the distance between the two horocycles causes one of the two arcs of horocycles (the one closer to the asymptotic point) to be twice as long as the other. These tiles may be packed along their line segment sides to fill out the annular region between the two horocycles, and to pack a nested family of congruent annuli between equally spaced horocycles on either side of them. When these annular packings line up so that each half of the inner horocyclic arc of a tile in one annulus matches up with the outer horocyclic arc of a tile in the next annulus, the result is thea binary tiling.{{r|df}}

[[File:Binary Tiling.png|thumb|A portion of thea binary tiling displayed in the [[Poincaré half-plane model]]. The horizontal lines correspond to horocycles in the hyperbolic plane, and the vertical line segments correspond to hyperbolic lines.]]

In the [[Poincaré half-plane model]] of hyperbolic geometry, with the ideal point chosen to be a [[point at infinity]] for the half-plane, hyperbolic lines asymptotic to this point are modeled as vertical rays, and horocycles asymptotic to this point are modeled as horizontal lines.{{r|rr}} This gives each tile the overall shape in the model of an axis-parallel square or rectangle.{{r|radin|fg}} For this model, the hyperbolic distance between points with the same <math>y</math>-coordinate is their Euclidean distance divided by <math>y</math>, while the hyperbolic distance between points with the same <math>x</math>-coordinate is the [[logarithm]] of the ratio of their <math>y</math>-coordinates.{{r|stahl}} From these facts one can calculate that successive horocycles of thea binary tiling, at hyperbolic distance <math>\ln 2</math>, are modeled by horizontal lines whose Euclidean distance from the <math>x</math>-axis doubles at each step, and that the two bottom half-arcs of a binary tile each equal the top arc.

[[File:Binary tiling straight.svg|thumb|Binary tiling with [[pentagonal tiling|convex pentagon tiles]], in the Poincaré half-plane model.]]

An alternative and combinatorially equivalent version of the tiling places its vertices at the same points, but connects them by hyperbolic line segments instead of horocyclic segments, so that each tile becomes a hyperbolic convex pentagon. This makes the tiling a proper [[pentagonal tiling]].{{r|fg|kari}}

If one considers only adjacencies between tiles of different sizes, omitting the side-to-side adjacencies, this adjacency pattern gives the tiles of thea binary tiling the structure of a [[binary tree]]. Representative points within each tile, connected according to this adjacency structure, give an embedding of an infinite binary tree as a [[hyperbolic tree]].{{r|kbvw}}

{{-}}

==Enumeration and aperiodicity==

The tiles of thea binary tiling are not all symmetric to each other; for instance, for the four tiles two levels below any given tile, no symmetry takes a middle tile to an outer tile. There are uncountably many different tilings of the hyperbolic plane by these tiles, even when they are modified by adding protrusions and indentations to force them to meet edge-to-edge. None of these different tilings are periodic (having a [[Cocompact group action|cocompact]] symmetry group),{{r|radin}} although some (such as the one in which there exists a line that is completely covered by tile edges) have a one-dimensional infinite symmetry group.{{r|df}} As a tile all of whose tilings are not fully periodic, the [[prototile]] of thea binary tiling solves an analogue of the {{not a typo|<!-- lowercase is intentional -->[[einstein problem]]}} in the hyperbolic plane.{{r|einstein}}

More strongly than having all tiles the same shape, all [[Heesch's problem|first coronas]] of tiles, the set of tiles touching a single central tile, have the same pattern of tiles (up to symmetries of the hyperbolic plane allowing reflections). For tilings of the Euclidean plane, having all first coronas the same implies that the tiling is periodic and [[isohedral tiling|isohedral]] (having all tiles symmetric to each other); the binary tilingtilings providesprovide a strong counterexample for the corresponding property in the hyperbolic plane.{{r|ds}}

Corresponding to the fact that these tilings are non-periodic but monohedral (having only one tile shape), the [[dual tiling]]s of these tilings are non-periodic but ''monocoronal'' (having the same pattern of tiles surrounding each vertex). These dual tilings are formed by choosing a reference point within each tile of thea binary tiling, and connecting pairs of reference points of tiles that share an edge with each other.{{r|fg}}

==Applications==

Line 34:

The original application for which Böröczky studies these tilings concerns the density of a discrete planar point set, the average number of points per unit area. This quantity is used, for instance, to study [[Danzer set]]s. For points placed one per tile in a [[monohedral tiling]] of the Euclidean plane, the density is inverse to the tile area. But for the hyperbolic plane, paradoxical issues ensue.{{r|radin|bor}} The tiles of a binary tiling can be grouped into three-tile subunits, with each subunit consisting of one tile above two more (as viewed in the Poincaré half-plane model). Points centered within the upper tile of each subunit have one point per subunit, for an apparent density equal to one third of the area of a binary tile. However, the same points and the same binary tiling can be regrouped in a different way, with two points per subunit, centered in the two lower tiles of each subunit, with two times the apparent density. This example shows that it is not possible to determine the density of a hyperbolic point set from tilings in this way.{{r|bor|bowen}}

Adjusting the distance between the two vertical sides of the tiles in thea binary tiling causes their area to vary, proportional to this distance. By making this distance arbitrarily small, this tiling can be used to show that the hyperbolic plane has tilings by congruent tiles of arbitrarily small area.{{r|agol}} [[Jarkko Kari]] has used a system of colorings of tiles from thea binary tiling, analogous to [[Wang tile]]s, to prove that determining whether a given system of hyperbolic [[prototile]]s can tile the hyperbolic plane is an [[undecidable problem]].{{r|kari}} Subdivisions of thea binary tiling that replace each tile by a [[grid graph]] have been used to obtain tight bounds on the [[Fine-grained reduction|fine-grained complexity]] of [[graph algorithm]]s.{{r|kmvww}} Recursive [[data structure]]s resembling quadtrees, based on the binary tiling, have been used for approximate [[nearest neighbor problem|nearest neighbor queries]] in the hyperbolic plane.{{r|kbvw}}

==Related patterns==

Line 42:

|image3=Baumslag-Solitar Cayley 3D.svg|caption3=Four sheets from the [[Cayley graph]] of the [[Baumslag–Solitar group]] <math>BS(1,2)</math>

}}

A 1957 print by [[M. C. Escher]], ''Regular Division of the Plane VI'', has this tiling as its underlying structure, with each tile of thea binary tiling (as seen in its quadtree form) subdivided into three right triangles.{{r|escher}} It is one of several Escher prints based on the half-plane model of the hyperbolic plane.{{r|dunham}} When interpreted as Euclidean shapes rather than hyperbolically, the tiles are squares and the subdivided triangles are isosceles right triangles. The print itself replaces each triangle by a stylized lizard.{{r|escher}}

The [[Smith chart]], from [[radio engineering]], resembles a binary tiling on the [[Poincaré disk model]] of the hyperbolic plane, and has been analyzed for its connections to hyperbolic geometry and to Escher's hyperbolic tilings.{{r|gupta}} It was first developed in the late 1930s by Tōsaku Mizuhashi,{{r|mizu}} [[Phillip Hagar Smith]],{{r|smith}} and Amiel R. Volpert.{{r|volpert}}

The [[Cayley graph]] of the [[Baumslag–Solitar group]] <math>BS(1,2)</math> can be decomposed into "sheets", planar structures with a geometry [[Quasi-isometry|quasi-isometric]] to the hyperbolic plane. The Cayley graph is embedded onto each sheet as the graph of vertices and edges of a binary tiling. At each level of thea binary tiling, there are two choices for how to continue the tiling at the next higher level. Any two sheets will coincide for some number of levels until separating from each other by following different choices at one of these levels, giving the sheets the structure of an infinite binary tree.{{r|cfm|as}}

The [[dual graph]] of thea binary tiling has a vertex for each tile, and an edge for each pair of tiles that share an edge. It takes the form of an infinite [[binary tree]] (extending infinitely both upwards and downwards, without a root) with added side-to-side connections between tree nodes at the same level as each other.{{r|df}} An analogous structure for finite [[complete binary tree]]s, with the side-to-side connections at each level extended from paths to cycles, has been studied as a [[network topology]] in [[parallel computing]], the ''ringed tree''.{{r|xtree}} Ringed trees have also been studied in terms of their [[Hyperbolic metric space|hyperbolic metric properties]] in connection with [[small-world network]]s.{{r|cfhm}}

A related tiling of the hyperbolic plane by [[Roger Penrose]] can be interpreted as being formed by adjacent pairs of binary tiles, one above the other, whose unions form L-shaped tiles. Like the binary tiling, it is weakly aperiodic.{{r|penrose}}

{{-}}