Recursive tilings and space-filling curves with little fragmentation

Herman Haverkort

Abstract


This paper defines the Arrwwid number of a recursive tiling (or space-filling curve) as the smallest number a such that any ball Q can be covered by a tiles (or curve fragments) with total volume O(volume(Q)). Recursive tilings and space-filling curves with low Arrwwid numbers can be applied to optimize disk, memory or server access patterns when processing sets of points in Rd. 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.

Full Text: PDF

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

ISSN: 1920-180X