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 2963780857 2071091006 1563955133
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. In his 1990 Inventiones paper, P. Jones characterized subsets of rectifiable curves in the plane via a multiscale sum of ( )-numbers. These ( )-numbers are geometric quantities measuring how far a given set deviates from a best fitting line at each scale and location. Jones’ result is a quantitative way of saying that a curve is rectifiable if and only if it has a tangent at almost every point. Moreover, computing this square sum for a curve returns the length of the curve up to multiplicative constant. K. Okikiolu extended his result from subsets of the plane to subsets of Euclidean space. G. David and S. Semmes extended the discussion to include sets of (integer) dimension larger than one, under the assumption of Ahlfors regularity and using a variant of Jones’ ( )-numbers. This variant has since been used by others to give structure theorems for rectifiable sets and to give upper bounds for the measure of a set. In this paper we give a version of P. Jones’ theorem for sets of arbitrary (integer) dimension lying in Euclidean space. Our main result is a lower bound for the d-dimensional Hausdorff measure of a set in terms of an analogous sum of ( )-type numbers. We also show an upper bound of this type. The combination of these results gives a Jones theorem for higher dimensional sets. While there is no assumption of Ahlfors regularity, or of a measure on the underlying set, there is an assumption of a lower bound on the Hausdorff content. We adapt David and Semmes’ version of Jones’ ( )-numbers by redefining them using a Choquet integral, allowing them to be defined for arbitrary sets (and not just sets of locally finite measure). A key tool in the proof is G. David and T. Toro’s parametrization of Reifenberg flat sets (with holes). Our study of tiling and packing with rectangles in two-dimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and motion estimation in video compression by block matching, among others. An example of the problems that we tackle is the following: given an n by n array A of positive numbers, find a tiling using at most p rectangles (that is, no two rectangles must overlap, and each array element must fall within some rectangle) that minimizes the maximum weight of any rectangle; here the "weight" of a rectangle is the sum of the array elements that fall within it. If the array A were one-dimensional, this problem could be easily solved by dynamic programming. We prove that in the two-dimensional case it is NP-hard to approximate this problem to within a factor of 1.25. On the other hand, we provide a near-linear time algorithm that returns a solution at most 2.5 times the optimal. Other rectangle tiling and packing problems that we study have similar properties: while it is easy to solve them optimally in one dimension, the two-dimensional versions become NP-hard. We design efficient approximation algorithms for these problems. This paper presents bounds on the quality of partitions induced by space-filling curves. We compare the surface that surrounds an arbitrary index range with the optimal partition in the grid, i.e. the square. It is shown that partitions induced by Lebesgue and Hilbert curves behave about 1.85 times worse with respect to the length of the surface. The Lebesgue indexing gives better results than the Hilbert indexing in worst case analysis. Furthermore, the surface of partitions based on the Lebesgue indexing are at most 5 2??3 times larger than the optimal in average case.