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

Author(s): 
Michael Bader
Publisher: 
Springer Verlag
Year: 
2013
ISBN: 
978-3-642-31045-4
Price (tentative): 
83,94 € (hardcover) 64,99 € (ebook) (net)
Short description: 

This is a gentle introduction to space filling curves. Emphasis is on the representation, implementation and application in computer science. A situation where they are useful is an (adaptive) subdivision scheme that is represented by a tree, and the space filling curve will then have to visit all the leaves of the tree in some order. Obvious applications are for example computer graphics and the numerical solution of partial differential equations. Additional material and scripts (maple, python) are made available online.

URL for publisher, author, or book: 
www.springer.com/978-3-642-31045-4
MSC main category: 
68 Computer science
MSC category: 
68W01
Other MSC categories: 
14H50, 65D18, 65M55, 65Y05, 68U99, 90C99
Review: 

The first chapter immediately makes clear what kind of applications one should have in mind. In computer graphics, as well as in the numerical solution of partial differential equations, some domain in 2D or 3D has to be subdivided into a finer grid, usually in an adaptive way. The parent-child relations are represented by a tree and the actual values one is interested in are located at the leaves of the tree. Hence when one wants to access the overall picture one will have to access all these leaves. Connecting the leaves in the order that they are visited gives a curve that runs through the whole domain. Since it is not clear in advance what the subdivision tree will look like, one needs a curve that is able to visit every coordinate in the domain: a space filling curve (SFC).

With this motivation, the next chapter gives a more formal definition, which is followed by two chapters that learn how to formally identify, and hence compute, the SFC. That can be by a formal grammar, defining strings that say which operations to perform to generate the curve. Once this is formally defined, it is not very difficult to switch to an algorithmic description which actually describes the affine maps that construct the vertices and edges of the SFC. These descriptions define recursive rules, which if they are applied at infinitum will make the curve to fill up the whole domain, which of course should be stopped after a finite depth of the recursion, in which case the curve is a polygon that can also be formally represented as a string of digits.

So far the examples have been the 2D Hilbert and Peano curves in a square. The next chapters extend the set of examples with Sierpinski curves (on triangles), the Lebesgue curve, and βΩ-curves first in 2D and later also in 3D. This brings us about halfway through the book. Assuming that the basics are now assimilated, the author moves on to the actual work. First the link with subdivision is made and it is explained how SFC are used to sequentialize spacetree grids. Then the focus is shifted to parallelization of the algorithm which is really necessary because these applications become large scale problems in practice. This requires an efficient partitioning of the SFC so that each subsection can be processed by a different processor. The load balancing among the processors, based on the SFC, can be quantified by using the Hölder continuity of the SFC which is discussed in the next chapter on locality measures and locality properties of SFC. In many applications, the subdivision is not on a rectangular but on a triangular and tetrahedral grids. So the Sierpinski curve makes a re-entry in a separate chapter. The remaining three chapters discuss further applications. As a case study, algorithms for matrix operations (matrix products) are investigated. The idea is that a SFC-way of traversing the matrix elements can result in a cache-efficient way of computing the result. Of course some elements of the caching mechanism of a computer are explained to justify the approach. Another case study is simulation on spacetree grids using SFC. This closes the loop with the very first chapter. The final chapter is an enumeration with a short guided tour of other possible applications: combinatorial problems, GIS systems, signal processing, and computer graphics.

It is clear that the author has a long teaching experience with this subject. He has found the right balance between motivation, rigor, application, implementation, in just the right pace to take the reader/student along climbing up the hill towards of increasing complexity as academic examples are left and one approaches the real life applications. Each chapter ends with some exercises (a selected set of solutions is added in an appendix) and there is a rather unusual insert-block "What's next", which sketches what could be the next step ahead, now that one has reached the current level of knowledge. This is exactly how one would end a lesson and give a preview of the next one.

Additional material including several (maple and python) scripts are available at www.space-filling-curves.org. At the moment of writing this review only maple scripts are available that generate examples that are illustrated in the book.

Reviewer: 
A. Bultheel
Affiliation: 
KU Leuven

Comments

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Copy the characters (respecting upper/lower case) from the image.
satunnaisuus