Jump to content

Binary tiling

Edit links
From Wikipedia, the free encyclopedia
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 lines in the hyperbolic plane.
Binary tiling on Poincare disk
A portion of a binary tiling displayed in the Poincare disk
Alternative version of the binary tiling with polygonal tiles, in the Poincaré half-plane model. This makes the tiling a proper pentagonal tiling.

In geometry, the binary tiling (sometimes called the Böröczky tiling)[1] is a tiling of the hyperbolic plane, resembling a quadtree over the Poincaré half-plane model of the hyperbolic plane. It was first studied mathematically in 1974 by Károly Böröczky [hu].[2][3][4]

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.[5]

Tiles

[edit]

In one version of the tiling, the tiles are shapes bounded by three congruent horocyclic segments (two of which are part of the same horocycle), and two line segments. All tiles are congruent. In the Poincaré half-plane model, the horocyclic segments are modeled as horizontal line segments (parallel to the boundary of the half-plane) and the line segments are modeled as vertical line segments (perpendicular to the boundary of the half-plane), giving each tile the overall shape in the model of a square or rectangle. However, in the hyperbolic plane, these tiles have five sides rather than four, and are not hyperbolic polygons, because their horocyclic edges are not straight. In the half-plane model, 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. Therefore, in order to make the two horocyclic segments on the lower horizontal edge of each tile each have equal length to the single horocyclic segment on the top edge of the tile, it should be placed with its top edge twice as far from the half-plane boundary as its bottom.[2]

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.[6] 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.[7]

Enumeration and aperiodicity

[edit]

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),[2][8] 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.[1] 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.[9]

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.[10]

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.[6]

Applications

[edit]

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.[3]

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.[11]

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

[edit]
Structure of Escher's Regular Division of the Plane VI
A Smith chart
Four sheets from the Cayley graph of the Baumslag–Solitar group

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.[5] It is one of several Escher prints based on the half-plane model of the hyperbolic plane.[12] 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.[5]

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

The Cayley graph of the Baumslag–Solitar group 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.[17][18]

References

[edit]
  1. ^ a b Dolbilin, Nikolai; Frettlöh, Dirk (2010). "Properties of Böröczky tilings in high-dimensional hyperbolic spaces" (PDF). European Journal of Combinatorics. 31 (4): 1181–1195. arXiv:0705.0291. doi:10.1016/j.ejc.2009.11.016.
  2. ^ a b c Radin, Charles (2004). "Orbits of Orbs: Sphere Packing Meets Penrose Tilings" (PDF). American Mathematical Monthly. 111 (2): 137–149. doi:10.2307/4145214. JSTOR 4145214.
  3. ^ a b Agol, Ian (January 26, 2018). "Smallest tile to tessellate the hyperbolic plane". MathOverflow.
  4. ^ Böröczky, Károly (1974). "Gömbkitöltések állandó görbületű terekben I". Matematikai Lapok (in Hungarian). 25: 265–306. As cited by Radin.
  5. ^ a b c Escher, M. C. (1989). "The regular division of the plane". Escher on Escher: Exploring the Infinite. Translated by Ford, Karin. Harry N. Abrams Inc. pp. 90–122. ISBN 0-8109-2414-5. See especially text describing Regular Division of the Plane VI, pp. 112 & 114, schematic diagram, p. 116, and reproduction of the print, p. 117.
  6. ^ a b Frettlöh, Dirk; Garber, Alexey (2015). "Symmetries of monocoronal tilings". Discrete Mathematics & Theoretical Computer Science. 17 (2): 203–234. arXiv:1402.4658. doi:10.46298/dmtcs.2142. MR 3411398.
  7. ^ a b Kisfaludi-Bak, Sándor; van Wordragen, Geert (2024). "A quadtree, a Steiner spanner, and approximate nearest neighbours in hyperbolic space". In Mulzer, Wolfgang; Phillips, Jeff M. (eds.). 40th International Symposium on Computational Geometry, SoCG 2024, June 11–14, 2024, Athens, Greece. LIPIcs. Vol. 293. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 68:1–68:15. arXiv:2305.01356. doi:10.4230/LIPICS.SOCG.2024.68.
  8. ^ Penrose, R. (1979–1980). "Pentaplexity: a class of nonperiodic tilings of the plane". The Mathematical Intelligencer. 2 (1): 32–37. doi:10.1007/BF03024384. MR 0558670.
  9. ^ Smith, David; Myers, Joseph Samuel; Kaplan, Craig S.; Goodman-Strauss, Chaim (2024). "An aperiodic monotile". Combinatorial Theory. 4 (1) 6. arXiv:2303.10798. doi:10.5070/C64163843. MR 4770585.
  10. ^ Dolbilin, Nikolai; Schulte, Egon (June 2004). "The local theorem for monotypic tilings". Electronic Journal of Combinatorics. 11 (2). Research Paper 7. doi:10.37236/1864. MR 2120102.
  11. ^ Kari, Jarkko (2007). "The tiling problem revisited (extended abstract)". In Durand-Lose, Jérôme Olivier; Margenstern, Maurice (eds.). Machines, Computations, and Universality, 5th International Conference, MCU 2007, Orléans, France, September 10–13, 2007, Proceedings. Lecture Notes in Computer Science. Vol. 4664. Springer. pp. 72–79. doi:10.1007/978-3-540-74593-8_6. ISBN 978-3-540-74592-1.
  12. ^ Dunham, Douglas (2012). "M. C. Escher's use of the Poincaré models of hyperbolic geometry" (PDF). In Bruter, Claude (ed.). Mathematics and Modern Art: Proceedings of the First ESMA Conference, held in Paris, July 19–22, 2010. Springer Proceedings in Mathematics. Vol. 18. Springer. pp. 69–77. doi:10.1007/978-3-642-24497-1_7. ISBN 9783642244971.
  13. ^ Gupta, Madhu S. (October 2006). "Escher's art, Smith chart, and hyperbolic geometry". IEEE Microwave Magazine. 7 (5): 66–76. doi:10.1109/mw-m.2006.247916.
  14. ^ Mizuhashi, Tōsaku (December 1937). "Sì duānzǐ huílù no inpīdansu hensei to seigō kairo no riron". J. Inst. Electrical Communication Eng. Japan. 1937 (12): 1053–1058.
  15. ^ Smith, P. H. (January 1939). "Transmission line calculator" (PDF). Electronics. 12 (1): 29–31.
  16. ^ Volpert, Amiel Rafailovich (February 1940). "Nomogramma dlya rascheta dlinnykh liniy". Proizvodstvenno-tekhnicheskiy Byulleten. 1940 (2): 14–18.
  17. ^ Cook, Briana; Freden, Eric M.; McCann, Alisha (2004). "A simple proof of a theorem of Whyte". Geometriae Dedicata. 108: 153–162. doi:10.1007/s10711-004-2304-3. MR 2112672.
  18. ^ Aubrun, Nathalie; Schraudner, Michael (2024). "Tilings of the hyperbolic plane of substitutive origin as subshifts of finite type on Baumslag-Solitar groups ". Comptes Rendus Mathématique Acad. Sci. Paris. 362: 553–580. arXiv:2012.11037. doi:10.5802/crmath.571. MR 4753921.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Binary_tiling&oldid=1240922389"