Computation of Lebesgue’s Space-Filling Curve

  • Arthur R Butz Dept. of Electrical and Computer Engineering, Northwestern University

Abstract

The means of realizing or approximating the Lebesgue space-filling curve (SFC) with binary arithmetic on a uniformly spaced binary grid are not obvious, one problem being its formulation in terms of ternary representations; that impediment can be overcome via use of a binary-oriented Cantor set.  A second impediment, namely the Devil’s Staircase feature, also created by the role of the Cantor set, can be overcome via the definition of a “working inverse”, thereby providing means of achieving compatibility with such a grid. The results indicate an alternative way to proceed, in realizing an approximation to Lebesgue’s SFC, which circumvents any complication raised by Cantor sets and is compatible with binary and integer arithmetic. Well-known constructions such as the z-curve or Morton order, sometimes considered in association with Lebesgue’s SFC, are treated as irrelevant.

Downloads

Download data is not yet available.

Author Biography

Arthur R Butz, Dept. of Electrical and Computer Engineering, Northwestern University

Department of Electrical and Computer Engineering, Northwestern University 2145 Sheridan Road, Evanston, IL 60208-3118

References

G. Peano. Sur une courbe, qui remplit toute une aire plane. Math. Ann., 36(1):157-160, 1890. https://doi.org/10.1007/BF01199438.

D. Hilbert. Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. An., 38(3): 459-460, 1891.

A. Bos and H. Haverkort, “Hyperorthogonal well-folded Hilbert curves,” J. Computational Geometry,” 7, 2, 145-190, 2016.

A.R. Butz, “Space filing curves and mathematical programming,” Information and Control, 12, 4, 314-330, April 1968.

A.R. Butz, “Convergence with Hilbert’s space filling curve,” J. Computer and System Sciences, 3, 128-146, 1969.

A.R. Butz, “Alternative algorithm for Hilbert’s space-filling curve,” IEEE Trans. Computers, April 1971, 424-426.

M. Bailova, J. Bouchala and Petr Vodstrcil, “Global Optimization Using Space Filling Curves,” Math. Analysis and Numerical Mathematics, 15, 2, June 2017.

D. Lera1 and Y. D. Sergeyev, GOSH: derivative-free global optimization using multi-dimensional space-filling curves, J Glob Optim Nov. 2017.

C. Schretter, Z. He, M. Gerber, N. Chopin, H. Niederreiter “Van der Corput and Golden Ratio Sequences Along the Hilbert Space-Filling Curve” Monte Carlo and Quasi-Monte Carlo Methods pp 531-544, online June 2016. https://link.springer.com/chapter/10.1007/978-3-319-33507-0_28.

Y.D. Sergeyev, R.G. Strongin and D. Lera, Introduction to Global Optimization Exploiting Space-Filling Curves, Springer, 2013.

A. Obulesu, V.V. Kumar, and L. Sumalatha, “Image Retrieval Based on Local Motif Patterns Code, Int. J. Image, Graphics and Signal Processing, 2018, 6, 68-78.

A.M. Reddy, V.V. Krishna and I. Sumalatha, “Face Recognition based on Cross Diagonal Complete Motif Matrix,” I.J. Image, Graphics and Signal Processing, 2018, 3, 59-66. Uses “Peano scan”.

Lin Fu, “Numerical methods for computational fluid dynamics - a new ENO paradigm and a new domain decomposition method”, dissertation, Technischen Universität München, Feb. 10, 2017.

M. Bader, Space-Filling Curves, Springer, Berlin, 2013. Bader’s book cites many examples of applications.

L. Arge, M de Berg, H. Haverkort, and K Yi, “The priority R-tree: a practically efficient and worst-case optimal R-tree.” ACM Trans. Algorithms,4(1), 30 (2008). Art. 9.

K. Gao and X. Mao, “Research on Massive Tile Data Management based on Hadoop,” 2016 2nd International Conference on Information Management (ICIM), London.

X. Guan, P. van Oostrom, and B. Cheng, “A Parallel N-Dimensional Space-Filling CurveLibrary and Its Application in Massive Point Cloud Management,” Int. J. Geo-Information, 2018, 7, 327+. Supports libraries using the Hilbert SFC and the Morton order

I. Kamel and C. Faloutsos, “Hilbert R-tree. An improved R-tree using fractals,” Proc. 20th VLDB Conf., Santiago, Chile, 1994. 500-509.

I. Kamel and C. Faloutsos. “On packing R-trees,” Conf. on Information and Knowledge Management, ACM, 1993, 490-499, 1993, 500-509.

J. Lawder, “The Application of Space-Filling Curves to the Storage and Retrieval of Multi-dimensional Data,” Ph.D. Thesis, Univ. of London, Dec.1999.

J. Banerjee, R. Ghatak and A. Karmakar, “A compact planar UWB MIMO diversity antenna with Hilbert fractal neutralization line for isolation improvement and dual band notch characteristics,” Conference: 2018 Emerging Trends in Electronic Devices and Computational Techniques (EDCT), March 2018. DOI: 10.1109/EDCT.2018.8405070.

H. Liu et. al. , “Dynamic Load Balancing Using Hilbert Space-Filling Curves for Parallel Reservoir Simulations” Society of Petroleum Engineers, SPE Reservoir Simulation Conference, 20-22 February, Montgomery, Texas, USA, 2017 (https://www.onepetro.org/conference-paper/SPE-182613-MS) .

L.N. Kanal, “Interactive pattern analysis and classification systems: a survey and commentary,” Proc. IEEE, vol. 60, no. 10, Oct. 1972, 1200-1215.

K. Davis and Y. Li, “Efficient 3D Inversion of Magnetic Data Via Octree Mesh Discretization, Space-filling Curves, And Wavelets.” Society of Exploration Geophysicists, 2010-1172 SEG Conference Paper – 2010, Jan. 1, 2010.

F. Ancona, A. De Gloria and R. Zunino, “Parallel VLSI architectures for cryptographic systems,” conference, 1997.

D.J. Hancock et. al. “An Investigation of Feedback Guided Dynamic Scheduling of Nested Loops”, 2000, Parallel Processing, 2000. Proceedings. 2000 International Workshops on , 21-24 Aug. 2000, Toronto. IEEE.

C. Muelder and K-L Ma, “Rapid Graph Layout Using Space Filling Curves,” IEEE Trans. Visualization and Computer Graphics, 14, 6 Nov./Dec. 2008.

W.D. Blecher, The Hilbert-Moore sequence Acoustic Noise optimized MR Imaging, dissertation, Universität Mannheim, 2008.

D. Moore. “Fast Hilbert curve generation, sorting, and range queries”. http://www.tiac.net/~sw/2008/10/Hilbert/moore/, 2000.

H. Sagan, Space-Filling Curves, Springer, Springer Science+Business Media, New York, 1994.

H. Haverkort, “Recursive Tilings and Space-Filling Curves with Little Fragmentation.” J. Computational Geometry, vol. 2, no. 1, 92-127, 2011.

H. Lebesgue, Leçons sur l’intégration, Gauthier-Villars, Paris, 1904 and 1928, (pp 44f). H. Lebesgue, “Sur les fonctions représentables analytiquement,” Journal de Mathématique Pures et Appliquées, vol. 6, no. 1 (1905), 139-216 (pp. 210f).

Published
2019-08-30
How to Cite
Butz, A. R. (2019). Computation of Lebesgue’s Space-Filling Curve. Computer Reviews Journal, 4, 1-17. Retrieved from http://purkh.com/index.php/tocomp/article/view/204
Section
Research Articles