Binary tiling: Difference between revisions

Revision as of 18:24, 21 September 2024

Revision as of 20:32, 21 September 2024

Line 9:

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.

Binary tilings were first studied mathematically in 1974 by {{ill|Károly Böröczky|hu|Böröczky Károly (matematikus, 1964)}}.{{r|radin|agol|bor}} Closely related tilings have been used since the late 1930s in the [[Smith chart]] for radio engineering, and appear in a 1957 print by [[M. C. Escher]].{{r|escher}}

==Tiles==

Line 32:

==Applications==

[[File:Binary tiling density.svg|thumb|upright=1.1|Is the average number of red points per tile 1/3 (left) or 2/3 (right)?]]

TheBinary originaltilings applicationwere forfirst whichstudied mathematically in 1974 by {{ill|Károly Böröczky|hu|Böröczky studiesKároly these(matematikus, tilings1964)}}.{{r|radin|agol|bor}} Böröczky was concernsinvestigating 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 a 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 a 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 a 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 binary tiling, have been used for approximate [[nearest neighbor problem|nearest neighbor queries]] in the hyperbolic plane.{{r|kbvw}}