Recursive tilings and space-filling curves with little fragmentation

H.J. Haverkort

Research output: Contribution to journalArticleAcademicpeer-review

58 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)92-127
JournalJournal of Computational Geometry
Volume2
Issue number1
Publication statusPublished - 2011

Fingerprint

Space-filling Curves
Tiling
Fragmentation
Tile
Set of points
Regular hexahedron
Fragment
Ball
Server
Optimise
Curve
Alternatives

Cite this

@article{d0085fa0f1044125a522ed323627cf32,
title = "Recursive tilings and space-filling curves with little fragmentation",
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.",
author = "H.J. Haverkort",
year = "2011",
language = "English",
volume = "2",
pages = "92--127",
journal = "Journal of Computational Geometry",
issn = "1920-180X",
publisher = "Macodrum library, Carleton University",
number = "1",

}

Recursive tilings and space-filling curves with little fragmentation. / Haverkort, H.J.

In: Journal of Computational Geometry, Vol. 2, No. 1, 2011, p. 92-127.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Recursive tilings and space-filling curves with little fragmentation

AU - Haverkort, H.J.

PY - 2011

Y1 - 2011

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

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

M3 - Article

VL - 2

SP - 92

EP - 127

JO - Journal of Computational Geometry

JF - Journal of Computational Geometry

SN - 1920-180X

IS - 1

ER -