Recursive tilings and space-filling curves with little fragmentation

2010/02/09 by Herman Haverkort, Haverkort, Herman
Computer Science · #Algorithms and Data Compression #Computational Geometry and Mesh Generation #Data Management and Algorithms #cs.CG

paper · pdf · doi:10.48550/arxiv.1002.1843

Manuscript accompanying abstract in EuroCG 2010, including full proofs, 20 figures, references, discussion etc

arxiv created 2010/02/09 · arxiv updated 2010/02/26

Abstract

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.

Related

• An optimal algorithm to generate tilings
• Sixteen space-filling curves and traversals for d-dimensional cubes and simplices
• Minimizing the Number of Tiles in a Tiled Rectangle
• The maximum discrete surface-to-volume ratio of space-filling curve partitions
• The Complexity of Tiling Problems