You are here

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

Michael Bader
Publication Date: 
Number of Pages: 
Texts in Computational Science and Engineering 9
[Reviewed by
Luiz Henrique de Figueiredo
, on

The well-known book Space-Filling Curves, by Hans Sagan (Springer, 1994) provides an excellent introduction to the mathematics and history of space-filling curves. Bader's book nicely complements Sagan's and provides an introduction to the algorithmics of space-filling curves. Anyone interested in or just curious about space-filling curves will enjoy both books.

The first half of the book contains detailed algorithms for constructing several classical space-filling curves, both in 2D and in 3D. The second half focuses on the applications of space-filling curves to scientific computing, especially the locality properties of space-filling curves to obtain fast algorithms that exploit the cache architectures of current computers.

The book has many color illustrations and can be used as a textbook and as reference monograph for research. The book has a web site containing code and errata.

Luiz Henrique de Figueiredo is a researcher at IMPA in Rio de Janeiro, Brazil. His main interests are numerical methods in computer graphics, but he remains an algebraist at heart. He is also one of the designers of the Lua language.

Two Motivating Examples.- 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.- Further Applications of Space-Filling Curves.- Solutions to Selected Exercises.- References.- Index  ​