
(pdf) Recurrence for Multidimensional SpaceFilling Functions (arXiv) 



Earlier Articles 


A spacefilling 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.
Spacefilling curves serve as a counterexample to lessthanrigorous
notions of dimension.
In addition to their mathematical importance, spacefilling curves
have applications to
dimension reduction,
mathematical programming [Butz 1968],
sparse multidimensional database indexing [Lawder 2000],
electronics [Zhu 2003], and
biology [Lieberman 2009].
The organizing power of spacefilling curves is even employed by the
xkcd webcomic "Map of the Internet".
Prof. Yaroslav D. Sergeyev
has written extensively about their application to
globaloptimization:

Strongin R.G., Sergeyev Ya.D. (2000),
Global optimization with nonconvex constraints: Sequential and
parallel algorithms,
Kluwer Academic Publishers, Dordrecht, 728 pp.

Yaroslav D. Sergeyev, Roman G. Strongin, Daniela Lera,
Introduction to global optimization exploiting spacefilling curves,
Springer, 2013.

Sergeyev Ya.D. (1995),
An information global optimization algorithm with local tuning,
SIAM Journal on Optimization, 5(4), 858870.

LeraD., Sergeyev Ya.D. (2010),
Lipschitz and Holder global optimization using spacefilling curves,
Applied Numerical Mathematics, 60(12), 115129.

LeraD., Sergeyev Ya.D. (2010),
An information global minimization algorithm using the local improvement technique,
Journal of Global Optimization, 48(1), 99112.
There is a surfeit of 2dimensional spacefilling curves, but
generalizing them to higher rank is not necessarily practical or even
possible. [Bongki 2001] attributes
generalization of spacefilling curves to any rank to
[Butz 1969]; who gives algorithms for both
the Hilbert and Peano spacefilling curves.
Properties
The properties we desire for spacefilling transforms are that they
be:
 spacefilling
 a continuous function whose range comes arbitrarily close to any
given point in the ndimensional unit hypercube.
 multidimensional
 exist for all ranks greater than one.
 selfsimilar
 can be defined as a nonterminating recurrence.
 Lebesgue measurepreserving.
 equal length intervals map to equal volumes.
 isotropic
 the lengths of axisaligned projections of the spacefilling
curve should be equal.
Algorithms
My latest paper:
Recurrence for Multidimensional SpaceFilling 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 spacefilling curves:
Hilbert SpaceFilling Curves gives a casual
description of an algorithm and its extension.
Recursive Formulation of Multidimensional
SpaceFilling Curves delves into the details of the
Hilbert curve recurrence and algorithm.
Peano SpaceFilling Curves gives the
description of an algorithm and its extension.
Hilbert SpaceFilling Playground Equipment


Bibliography
 [Butz 1968]

A. R. Butz.
Space filling curves and mathematical programming.
Information and Control, 12:314330, 1968.
 [Butz 1969]

A. R. Butz,
Convergence with Hilbert's space filling curve,
J. Comput. Sys. Sci., vol. 3, May 1969, pp 128146.
 [Butz 1971]

A. R. Butz,
Alternative Algorithm for Hilbert's SpaceFilling Curve,
IEEE Trans. Comp., April, 1971, pp 424426.
 [HAKMEM]

M. Beeler, R.W. Gosper, R.Schroeppel,
ITEM 115 (Gosper),
HAKMEM, AIM 239,
MIT Artificial Intelligence Laboratory, 1972
 [Meyerson 1998]

Mark D. Meyerson,
Visualizing SpaceFilling 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 Multidimensional 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,
1999
 [JL1_00]

J.K.Lawder,
Calculation of Mappings Between One and ndimensional Values Using the Hilbert Spacefilling 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 Spacefilling Curves for MultiDimensional Indexing,
BNCOD 17, Lectures Notes in Computer Science, vol. 1832,
pp 2035, Springer 2000.
 [Bongki 2001]

Bongki Moon, H.V. Jagadish, Christos Faloutsos, and Joel Salz,
Analysis of the Clustering Properties of Hilbert Spacefilling Curve,
IEEE Trans. on Knowledge and Data Engineering (IEEETKDE),
vol. 13, no. 1, pp. 124141, Jan./Feb. 2001.
 [Zhu 2003]

Jinhui Zhu, Ahmad Hoorfar, and Nader Engheta,
Bandwidth, CrossPolarization, and FeedPoint Characteristics of Matched Hilbert Antennas,
pp. 25, IEEE ANTENNAS AND WIRELESS PROPAGATION LETTERS, VOL. 2, 2003.
 [Jin 2005]

Guohua Jin and John MellorCrummey,
SFCGen: A Framework For Efficient Generation Of MultiDimensional SpaceFilling Curves By Recursion,
ACM Transactions on Mathematical Software,
Volume 31(1):pp. 120  148. 2005.
 [Jin 2005b]

Guohua Jin and John MellorCrummey,
Using Spacefilling Curves for Computation Reordering,
Proceedings of the Los Alamos Computer Science Institute Sixth Annual
Symposium. published on CD. 2005
 [Lieberman 2009]

LiebermanAiden & Van Berkum et al.,
Comprehensive Mapping of LongRange 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.

  Geometry

 agj @ alum.mit.edu
 Go Figure!
