|
(pdf) Recurrence for Pandimensional Space-Filling Functions (arXiv) |
|
|
|
Earlier Articles |
|
|
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.
Properties
The properties we desire for space-filling transforms are that they
be:
- space-filling
- a continuous function whose range comes arbitrarily close to any
given point in the n-dimensional unit hypercube.
- multidimensional
- exist for all ranks greater than one.
- self-similar
- can be defined as a nonterminating recurrence.
- Lebesgue measure-preserving.
- equal length intervals map to equal volumes.
- isotropic
- the lengths of axis-aligned projections of the space-filling
curve should be equal.
Algorithms
My latest paper:
Recurrence for Pandimensional 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
|
---|
Bibliography
- [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.
- [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 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,
1999
- [JL1_00]
-
J.K.Lawder,
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,
pp. 2-5, IEEE ANTENNAS AND WIRELESS PROPAGATION LETTERS, VOL. 2, 2003.
- [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.
|
| | Geometry
|
| agj @ alum.mit.edu
| Go Figure!
|