Binary tiling

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 the Böröczky tiling) is a tiling of the hyperbolic plane, resembling a quadtree over the Poincaré half-plane model of the hyperbolic plane. The tiles may be convex pentagons, or they may be shapes with four sides, alternating between line segments and curved arcs.

There are uncountably many combinatorially binary tilings for a given shape of tile. They are all weakly 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.

Binary tilings were first studied mathematically in 1974 by Károly Böröczky. Closely related tilings have been used since the late 1930s in the Smith chart for radio engineering, and in a 1957 print by M. C. Escher.

Tiles

In one version of the tiling, each tile is a subset of the hyperbolic plane that lies between two hyperbolic lines and two horocycles that are all asymptotic to the same ideal point, with the horocycles at distance $\log 2$ 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 $\log 2$ 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 the binary tiling.

A portion of the 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 line. This gives each tile the overall shape in the model of an axis-parallel square or rectangle. However, it is not a hyperbolic polygon, because some of its sides are horocycle arcs rather than line segments. In this model, the hyperbolic length of a horizontal horocyclic segment is its Euclidean length in the model, divided by its Euclidean distance from the half-plane boundary. The hyperbolic distance between two horocycles is the logarithm of the ratio of their Euclidean distances from the boundary. Therefore, in order to make the two horocyclic arc on the lower horizontal edge of each tile each have equal length to the single horocyclic arc on the top edge of the tile, and to make these two arcs be at hyperbolic distance $\ln 2$ from each other, they must be placed with the top arc twice as far from the half-plane boundary as the bottom arc.

Alternative version of the binary tiling with polygonal tiles, in the Poincaré half-plane model. This makes the tiling a proper pentagonal tiling.

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. In this form of the tiling, the tiles do not appear as rectangles in the halfplane model, and the horocycles formed by horizontal sequences of edges are replaced by apeirogons.

If one considers only adjacencies between tiles of different sizes, omitting the side-to-side adjacencies, this adjacency pattern gives the tiles of the 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.

Enumeration and aperiodicity

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 symmetry group), 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. As a tile all of whose tilings are not fully periodic, the prototile of the binary tiling solves an analogue of the einstein problem in the hyperbolic plane.

More strongly than having all tiles the same shape, all 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 (having all tiles symmetric to each other); the binary tiling provides a strong counterexample for the corresponding property in the hyperbolic plane.

Corresponding to the fact that these tilings are non-periodic but monohedral (having only one tile shape), the dual tilings 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 the binary tiling, and connecting pairs of reference points of tiles that share an edge with each other.

Applications

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 (defined using a lim sup over arbitrarily large disks, and used, e.g., to study Danzer sets). For the Euclidean plane, this is well-defined, and invariant under bounded displacements of the points. For points placed one per tile in a monohedral tiling, the density is inverse to the tile area. But for the hyperbolic plane, paradoxical issues ensue. If one places a point interior to each tile of a binary tiling, the apparent density of the resulting point set is inverse to the area of the tiles. However, if the same point set is displaced by a bounded distance of $\ln 2$ towards the asymptotic ideal point of the tiling, the displaced point set will have two points per tile, doubling its apparent density. Therefore, it is not possible to define the density of a hyperbolic point set in a way that is invariant under bounded displacements.

Adjusting the distance between the two vertical sides of the tiles in the 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.

Jarkko Kari has used a system of colorings of tiles from the binary tiling, analogous to Wang tiles, to prove that determining whether a given system of hyperbolic prototiles can tile the hyperbolic plane is an undecidable problem.

Recursive data structures resembling quadtrees, based on the binary tiling, have been used for approximate nearest neighbor queries in the hyperbolic plane.

Related patterns

Structure of Escher's Regular Division of the Plane VI

A Smith chart

Four sheets from the Cayley graph of the Baumslag–Solitar group $BS(1,2)$

A 1957 print by M. C. Escher, Regular Division of the Plane VI, has this tiling as its underlying structure, with each tile of the binary tiling (as seen in its quadtree form) subdivided into three right triangles. It is one of several Escher prints based on the half-plane model of the hyperbolic plane. 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.

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. It was first developed in the late 1930s by Tōsaku Mizuhashi, Phillip Hagar Smith, and Amiel R. Volpert.

The Cayley graph of the Baumslag–Solitar group $BS(1,2)$ can be decomposed into "sheets", planar structures with a geometry 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 the 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.