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 inRd. 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


ISSN: 1920-180X