Logo PTI Logo FedCSIS

Communication Papers of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 37

A simple algorithm for computing a multi-dimensional the Sierpiński space-filling curve generalization

DOI: http://dx.doi.org/10.15439/2023F5773

Citation: Communication Papers of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 37, pages 265–270 ()

Full text

Abstract. Transforming multidimensional data into a one-dimensional sequence using space-filling curves, such as the Hilbert curve, has been studied extensively in many papers. This work provides a systematic presentation of the construction of an arbitrarily accurate multidimensional space-filling curve approximation which is a generalization of the Sierpi\'nski space-filling curve. At the same time, according to the space-filling curve construction, we present a simple algorithm for determining one of the counter-images on a unit interval of a data point lying in a multidimensional cube. The paper contains numerical algorithms for local generation of the curve approximation and determination of the quasi inverse of a data point used to transform multidimensional data into the one-dimensional form.

References

  1. Bader M., Schraufstetter S., Vigh C., Behrens J.: Memory effcient adaptive mesh generation and implementation of multigrid algorithms using Sierpinski curves, International Journal of Computational Science and Engineering, 4(1), 1742–7193, (2008).
  2. Bader M.: Space-Filling Curves. An Introduction with Applications in Scientific Computing. Springer-Verlag Berlin Heidelberg (2013).
  3. Bartholdi J. J., Platzman L. K.: Heuristics based on spacefilling curves for combinatorial problems in Euclidean space, Management Sci., 34, 291–305, (1988).
  4. G. Bhatnagar, Q. M. J. Wu, and B. Raman: Image and video encryption based on dual space-filling curves, Computing Journal,55(6), 667–685, (2012).
  5. Bungartz H.-J., M. Mehl M., T. Neckel T., and T. Weinzierl T.: The PDE framework Peano applied to fluid dy- namics: an efficient implementation of a parallel multiscale fluid dynamics solver on octreelike adaptive Cartesian grids, Computational Mechanics, 46(1), 103–114, (2010).
  6. Butz A.R.: Alternative algorithm for Hilbert’s space-filling curve, IEEE Trans. on Computing, 20, 424–426 (1971).
  7. Falconer K.: , Fractal Geometry: mathematical foundations and applications, John Wiley & Sons Ltd., Chichester, 3-nd ed.(2014).
  8. Fisher,R.A.: The use of multiple measurements in taxonomic problems, Annual Eugenics, 7 II, 179–188 (1936).
  9. Gilbert E. N. :, Gray codes and Paths on the n-cube, Bell System Tech. J., 37, 815–826 (1957).
  10. Gotsman C., Lindenbaum M.:, On the metric properties of discrete space-filling curves, IEEE Trans. on Image Processing, 5(5), 794–797 (1996).
  11. He Z. and Owen A. B.: Extensible grids: uniform sampling on a space filling curve, Journal of the Royal Statistical Society. Series B (Statistical Methodology) 78(4), 917–935, (2016).
  12. Hilbert D. : Ueber die stetige Abbildung einer Linie auf ein Flaechenschtueck, Mathematische Annalen 38, 459–469, (1891).
  13. Kim, H.I.; Hong, S.; Chang, J.W.: Hilbert curve-based cryptographic transformation scheme for spatial query processing on outsourced private data. Data & Knowledge Engineering 104 (C), 32–44 (2016).
  14. Kumar G.S., Pandithevan P., Ambatti A.R.: Fractal raster tool paths for layered manufacturing of porous objects, Virtual and Physical Prototyping 4(2),91–104, (2009).
  15. Lawder J. K. and King P. J. H.:Using space-filling curves for multidimensional indexing, in Proc. 17th BNCOD, in Lecture Notes in Computer Science, 1832. 20–35, (2000)
  16. Lian, H., Qiu, W., Yan, D., Guo J., Li Z., Tang, P.: Privacy-preserving spatial query protocol based on the Moore curve for location-based service, Computers & Security, 96, 101845, (2020).
  17. Melian, S., Brix, K., Müller, S., Schieffer, G. (2011). Space-Filling Curve Techniques for Parallel, Multiscale-Based Grid Adaptation: Concepts and Applications. In: Kuzmin, A. (eds) Computational Fluid Dynamics 2010. Springer, Berlin, Heidelberg
  18. Milne S.C.:, Peano Curves and Smoothness of Functions, Advances in Mathematics 35 ,129-157 (1980).
  19. Moon, B., Jagadish, H.V., Faloutsos, C., Saltz, J.H.: Analysis of the clustering properties of the hilbert space-filling curve. IEEE Trans Knowl Data Eng 13 (1), 124–141 (2001). http://dx.doi.org/10.1109/69.908985
  20. Moore E. H.:, On certain crinkly curves, Trans. Amer. Math. Soc., 1 (1900), pp. 72–90.
  21. Nair S.H., Sinha A., Vachhani L.: Hilbert’s space-filling curve for regions with holes, Proc. of IEEE Conference on Decision and Control, 313–319 (2017).
  22. Ouni, T., Lassoued, A. and Abid M.: Lossless image compression using gradient based space filling curves (G-SFC). Signal, Image and Video Processing 9, 277–293 (2015).
  23. O’Shaughnessy S., Sheridan S.:Image-based malware classification hybrid framework based on space-filling curves, Computers & Security, 116, 102660, (2022).
  24. Patrick E.D., Anderson D.R., Bechtel F.K., Mapping multidimensional space to one dimension for computer output display, IEEE Trans. on Comput. 17, 949–953, (1968).
  25. Peano G.:, Sur une courbe qui remplit toute une aire plane, Math. Ann., 36, 157–160 (1890).
  26. L. K. Platzman and J. J. Bartholdi:, Spacefilling Curves and the Planar Traveling Salesman Problem, Journal of ACM, 36, 719–737 (1989).
  27. Sagan H., Space-filling Curves, Springer-Verlag, New York, 1994.
  28. Schrack G., Stocco L. : Generation of Spatial Orders and Space-Filling Curves, IEEE Trans. on Image Processing, 24(6, 1791–1800, (2015).
  29. S. Sharma, K. Hari and G. Leus, Space filling curves for MRI sampling in IEEE ICASSP, 1115–1119, (2020).
  30. Sierpiński W.:, O pewnej krzywej wypełniaja̧cej kwadrat. Sur une nouvelle courbe continue qui remplit toute une aire plane., Bulletin de l‘Acad. des Sciences de Cracovie A.,463–478, (1912).
  31. Sergeyev, Y.D.: An information global optimization algorithm with local tuning. SIAM J. Optim. 5, 858–870 (1995)
  32. Sergeyev Y.D., Strongin R.G. , Lera D.: Introduction to Global Optimization Exploiting Space-Filling Curves, Springer New York Heidelberg Dordrecht London (2012).
  33. Sergeyev Y.D., ·Maria Chiara Nasso M.C.,Lera D.: Numericalmethods using two different approximations of space-filling curves for black-box global optimization, Journal of Global Optymization, published online 08.08.2022 https://doi.org/10.1007/s10898-022-01216-1, published online 08.08.2022.
  34. Skubalska-Rafajłowicz E.:, Applications of the space-filling curves with data driven measure–preserving property, Nonlinear Analysis, Theory, Methods and Applications, 30(3), 1305–1310, (1997).
  35. Skubalska-Rafajłowicz E., Rafajłowicz E.: Searching for optimal experimental designs using space-filling curves Applied Mathematics and Computer Science. 8(3) 647–656 (1998).
  36. Skubalska-Rafajłowicz E., Rafajłowicz E.: Space-filling curves in generating equidistrubuted sequences and their properties in sampling of images W: Signal processing / ed. by Sebastian Miron. Vukovar : InTeh, 131–149 (2010.
  37. Skubalska-Rafajłowicz E.:, Krzywe wypełniaja̧ce w rozwia̧zywaniu wielowymiarowych problemów decyzyjnych, Wydawnictwo Politechniki Wrocławskiej, 2001.
  38. Skubalska-Rafajłowicz E.:, Pattern recognition algorithm based on space-filling curves and orthogonal expansion, IEEE Trans. on Information Theory 47(5) 1915–1927, (2001).
  39. Skubalska-Rafajłowicz E.: A new method of estimation of the box-counting dimension of multivariate objects using space-filling curves. Nonlinear Analysis, Theory, Methods & Applications. Series A, Theory and Methods. 63 (5–7), 1281–1287,(2005).
  40. Skubalska-Rafajłowicz E., Rafajłowicz E.: Sampling multidimensional signals by a new class of quasi-random sequences. Multidimensional Systems and Signal Processing. 23 (1/2) 237–253, (2012).
  41. Steele J. M.: Efficacy of Spacefilling Heuristics in Euclidean Combinatorial Optimization, Operations Research Letters 8 , 237–239, (1989).
  42. Vogiatzis D. and Tsapatsoulis N.:Clustering Microarray Data with Space Filling Curves, in Proceedings of the 7th international workshop on Fuzzy Logic and Applications: Applications of Fuzzy Sets Theory, LNAI 4578, 529–536, (2007).
  43. Zhou L., C. R. Johnson and D. Weiskopf: Data-Driven Space-Filling Curves, IEEE Transactions on Visualization and Computer Graphics, 27(2) 1591–1600, (2021).