This paper defines the Arrwwid number of a recursive tiling (or space-filling curve) as the smallest number w such that any ball Q can be covered by w tiles (or curve sections) with total volume O(vol(Q)). Recursive tilings and space-filling curves with low Arrwwid numbers can be applied to optimise disk, memory or server access patterns when processing sets of points in d-dimensional space. This paper presents recursive tilings and space-filling curves with optimal Arrwwid numbers. For d >= 3, we see that regular cube tilings and space-filling curves cannot have optimal Arrwwid number, and we see how to construct alternatives with better Arrwwid numbers.
The Arrwwid number, as defined above, does not have this limitation: it admits a comparison between curves with different underlying tilings. Nevertheless , too, only studied curves based on the tiling with four squares per square @cite_7 . The Arrwwid number of such a tiling is four. studied what can be achieved by controlling the order in which the tiles are stored: they presented an ordering scheme, the space-filling curve, that guarantees that whenever four tiles are needed, at least two of them are consecutive on disk. Thus these four tiles can be divided into at most three sets such that the tiles within each set are consecutive, and thus the Arrwwid number of the space-filling curve is three. also proved that one cannot do better: no ordering scheme of this particular tiling has Arrwwid number less than three.
@cite_7
2721204918
We are given a two-dimensional square grid of size N×N, where N∶=2n and n≥0. A space filling curve (SFC) is a numbering of the cells of this grid with numbers from c+1 to c+N2, for some c≥0. We call a SFC recursive (RSFC) if it can be recursively divided into four square RSFCs of equal size. Examples of well-known RSFCs include the Hilbert curve, the z-curve, and the Gray code.