Content deleted Content added
→Related patterns: +wl |
fine-grained complexity |
||
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 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.{{r|agol}} [[Jarkko Kari]] has used a system of colorings of tiles from the 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 the 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 205:
| year = 2024| doi-access = free
}}</ref>
<ref name=kmvww>{{citation
| last1 = Kisfaludi-Bak | first1 = Sándor
| last2 = Masaríková | first2 = Jana
| last3 = van Leeuwen | first3 = Erik Jan
| last4 = Walczak | first4 = Bartosz
| last5 = Wegrzycki | first5 = Karol
| editor1-last = Mulzer | editor1-first = Wolfgang
| editor2-last = Phillips | editor2-first = Jeff M.
| arxiv = 2310.11283
| contribution = Separator theorem and algorithms for planar hyperbolic graphs
| doi = 10.4230/LIPIcs.SoCG.2024.67
| pages = 67:1–67:17
| publisher = Schloss Dagstuhl - Leibniz-Zentrum für Informatik
| series = LIPIcs
| title = 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece
| volume = 293
| year = 2024}}</ref>
<ref name=mizu>{{cite journal
| |||