space-filling curve playground equipment

Multidimensional Space-Filling Curves

several generations of space-filling curve (pdf) Recurrence for Multidimensional Space-Filling Functions (arXiv)
color catalog Color Space Dimension Reduction
The Performance of Space-Filling Curves for Dimension Reduction
October 9, 2009 Science cover Lieberman-Aiden & Van Berkum et al.
Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome
Supporting Online Material (free access)
Earlier Articles
serpentine line Hilbert Space-Filling Curves
Recursive Formulation of Multidimensional Hilbert Space-Filling Curves
rectangular spiral Peano Space-Filling Curves

A space-filling curve is a parameterized, injective function which maps a unit line segment to a continuous curve in the unit square, cube, hypercube, etc, which gets arbitrarily close to a given point in the unit cube as the parameter increases.

Space-filling curves serve as a counterexample to less-than-rigorous notions of dimension. In addition to their mathematical importance, space-filling curves have applications to dimension reduction, mathematical programming [Butz 1968], sparse multi-dimensional database indexing [Lawder 2000], electronics [Zhu 2003], and biology [Lieberman 2009]. The organizing power of space-filling curves is even employed by the xkcd webcomic "Map of the Internet".

Prof. Yaroslav D. Sergeyev has written extensively about their application to global-optimization:

Strongin R.G., Sergeyev Ya.D. (2000),
Global optimization with non-convex constraints: Sequential and parallel algorithms,
Kluwer Academic Publishers, Dordrecht, 728 pp.
Yaroslav D. Sergeyev, Roman G. Strongin, Daniela Lera,
Introduction to global optimization exploiting space-filling curves,
Springer, 2013.
Sergeyev Ya.D. (1995),
An information global optimization algorithm with local tuning,
SIAM Journal on Optimization, 5(4), 858-870.
LeraD., Sergeyev Ya.D. (2010),
Lipschitz and Holder global optimization using space-filling curves,
Applied Numerical Mathematics, 60(1-2), 115--129.
LeraD., Sergeyev Ya.D. (2010),
An information global minimization algorithm using the local improvement technique,
Journal of Global Optimization, 48(1), 99-112.

There is a surfeit of 2-dimensional space-filling curves, but generalizing them to higher rank is not necessarily practical or even possible. [Bongki 2001] attributes generalization of space-filling curves to any rank to [Butz 1969]; who gives algorithms for both the Hilbert and Peano space-filling curves.


The properties we desire for space-filling transforms are that they be:

a continuous function whose range comes arbitrarily close to any given point in the n-dimensional unit hypercube.
exist for all ranks greater than one.
can be defined as a nonterminating recurrence.
Lebesgue measure-preserving.
equal length intervals map to equal volumes.
the lengths of axis-aligned projections of the space-filling curve should be equal.


My latest paper: Recurrence for Multidimensional Space-Filling Functions (arXiv) (pdf) describes an algorithmic technique which produces both Peano and Hilbert curves and their generalizations to higher dimensions.

Three other pages are earlier articles about space-filling curves:

Hilbert Space-Filling Curves gives a casual description of an algorithm and its extension.

Recursive Formulation of Multidimensional Space-Filling Curves delves into the details of the Hilbert curve recurrence and algorithm.

Peano Space-Filling Curves gives the description of an algorithm and its extension.

Hilbert Space-Filling Playground Equipment


[Butz 1968]
A. R. Butz.
Space filling curves and mathematical programming.
Information and Control, 12:314-330, 1968.
[Butz 1969]
A. R. Butz,
Convergence with Hilbert's space filling curve,
J. Comput. Sys. Sci., vol. 3, May 1969, pp 128-146.
[Butz 1971]
A. R. Butz,
Alternative Algorithm for Hilbert's Space-Filling Curve,
IEEE Trans. Comp., April, 1971, pp 424-426.
M. Beeler, R.W. Gosper, R.Schroeppel,
ITEM 115 (Gosper), HAKMEM, AIM 239,
MIT Artificial Intelligence Laboratory, 1972
[Meyerson 1998]
Mark D. Meyerson,
Visualizing Space-Filling Curves with Fractals (As Limits of Curves of Continuously Varying Dimension),
Communications in Visual Mathematics, vol 1, no 1, August 1998.
[Alber 1998]
Jochen Alber and Rolf Niedermeier,
On Multi-dimensional Hilbert Indexings,
COCOON '98: Proceedings of the 4th Annual International Conference on Computing and Combinatorics
Lecture Notes in Computer Science, Springer, 1998.
[Moore 1999]
D. Moore,
Fast Hilbert Curve Generation, Sorting, and Range Queries,
Calculation of Mappings Between One and n-dimensional Values Using the Hilbert Space-filling Curve,Research Report JL1/00,
School of Computer Science and Information Systems, Birkbeck College, University of London, 2000
[Lawder 2000]
J.K.Lawder, P.J.H.King,
Using Space-filling Curves for Multi-Dimensional Indexing,
BNCOD 17, Lectures Notes in Computer Science, vol. 1832,
pp 20-35, Springer 2000.
[Bongki 2001]
Bongki Moon, H.V. Jagadish, Christos Faloutsos, and Joel Salz,
Analysis of the Clustering Properties of Hilbert Space-filling Curve,
IEEE Trans. on Knowledge and Data Engineering (IEEE-TKDE),
vol. 13, no. 1, pp. 124-141, Jan./Feb. 2001.
[Zhu 2003]
Jinhui Zhu, Ahmad Hoorfar, and Nader Engheta,
Bandwidth, Cross-Polarization, and Feed-Point Characteristics of Matched Hilbert Antennas,
[Jin 2005]
Guohua Jin and John Mellor-Crummey,
SFCGen: A Framework For Efficient Generation Of Multi-Dimensional Space-Filling Curves By Recursion,
ACM Transactions on Mathematical Software,
Volume 31(1):pp. 120 - 148. 2005.
[Jin 2005b]
Guohua Jin and John Mellor-Crummey,
Using Space-filling Curves for Computation Reordering,
Proceedings of the Los Alamos Computer Science Institute Sixth Annual Symposium. published on CD. 2005
[Lieberman 2009]
Lieberman-Aiden & Van Berkum et al.,
Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome,
Science 326, pp. 289 - 293 (2009).

Copyright © 2003, 2005, 2009, 2014 Aubrey Jaffer

I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory.  My actions and comments do not reflect in any way on MIT.
agj @
Go Figure!