Binary tiling: Difference between revisions

Revision as of 03:59, 28 October 2024

Revision as of 04:13, 28 October 2024

Line 44:

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}} Böröczky was investigating 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}}

Another application involves the area of tiles in a monohedral tiling.

AdjustingIn defining the binary tilings, there is a free parameter, the distance between the two vertical sides of the tiles. All tiles in a binarysingle tiling causeshave theirequal areahyperbolic to varyareas, proportionalbut toif this distance. Bychanges, makingthe this(equal) distancearea arbitrarilyof smallall the tiles will also change, in proportion. Choosing this tilingdistance canto be usedarbitrarily tosmall showshows 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}}

==Related patterns==