Bader M. Space-Filling Curves: An Introduction with Applications in Scientific Computing

Springer-Verlag, Berlin, Heidelberg, 2013. — 285 p. — (Texts in Computational Science and Engineering 9) — ISBN: 9783642310454Space-filling curves started their “lives” as mathematical curiosities, at the end of the nineteenth century. The idea that a one-dimensional curve may completely cover an area or a volume was, at that time, completely novel and counterintuitive. Together with their relatives – such as Koch curves, the Cantor Set, and similar constructions – space-filling curves contradicted the then existing notion of a curve and of continuity and differentiability of functions (being continuous everywhere, but nowhere differentiable), and demanded new concepts in set theory and dimensionality. As a result, space-filling curves became almost notorious as “topological monsters”, and were studied by a good number of highly influential mathematicians, such as Peano, Hilbert, Lebesgue, Sierpinski, and others. The book of Hans Sagan provides an excellent introduction and overview of these mathematical aspects of space-filling curves, as well as on their history.Two Motivating Examples: Sequential Orders on Quadtrees and Multidimensional Data Structures
How to Construct Space-Filling Curves
Grammar-Based Description of Space-Filling Curves
Arithmetic Representation of Space-Filling Curves
Approximating Polygons
Sierpinski Curves
Further Space-Filling Curves
Space-Filling Curves in 3D
Refinement Trees and Space-Filling Curves
Parallelisation with Space-Filling Curves
Locality Properties of Space-Filling Curves
Sierpinski Curves on Triangular and Tetrahedral Meshes
Case Study: Cache Efficient Algorithms for Matrix Operations
Case Study: Numerical Simulation on Spacetree Grids Using Space-Filling Curves
App. Solutions to Selected Exercises