Abstract
Space-filling curves are a useful tool for fast multi-dimensional space indexing, dimension reduction, and fast optimization of complex problems. Several curves such as Hilbert, Peano, Gray, Morton or Z-order were discovered, and their properties and features were intensely studied. In this paper, a new space-filling curve is described, and its features are analyzed and compared with the other space-filling curves. The novel algorithm for a space-filling curve is based on the Residue Number System that is extensively studied during the last thirty years. The proposed curve has specific behavior and may be controlled by several parameters.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Asano, T., Ranjan, D., Roos, T., Welzl, E., Widmayer, P.: Space-filling curves and their use in the design of geometric data structures. Theoret. Comput. Sci. 181(1), 3–15 (1997)
Bially, T.: Space-filling curves: their generation and their application to bandwidth reduction. IEEE Trans. Inf. Theor. 15(6), 658–664 (1969)
Butz, A.R.: Space filling curves and mathematical programming. Inf. Control 12(4), 314–330 (1968)
Butz, A.R.: Alternative algorithm for Hilbert’s space-filling curve. IEEE Trans. Comput. 100(4), 424–426 (1971)
Chen, H.L., Chang, Y.I.: Neighbor-finding based on space-filling curves. Inf. Syst. 30(3), 205–226 (2005)
Gotsman, C., Lindenbaum, M.: On the metric properties of discrete space-filling curves. IEEE Trans. Image Process. 5(5), 794–797 (1996)
Gottschau, M., Haverkort, H., Matzke, K.: Reptilings and space-filling curves for acute triangles. arXiv preprint arXiv:1603.01382 (2016)
Jagadish, H.V.: Analysis of the Hilbert curve for representing two-dimensional space. Inf. Process. Lett. 62(1), 17–22 (1997)
Jasrasaria, D., Pyzer-Knapp, E.O., Rappoport, D., Aspuru-Guzik, A.: Space-filling curves as a novel crystal structure representation for machine learning models. arXiv preprint arXiv:1608.05747 (2016)
Kochhar, J.S., Foster, B.T., Heragu, S.S.: Hope: a genetic algorithm for the unequal area facility layout problem. Comput. Oper. Res. 25(7), 583–594 (1998)
Liang, J.Y., Chen, C.S., Huang, C.H., Liu, L.: Lossless compression of medical images using Hilbert space-filling curves. Comput. Med. Imaging Graph. 32(3), 174–182 (2008)
Liu, X.: Four alternative patterns of the Hilbert curve. Appl. Math. Comput. 147(3), 741–752 (2004)
Ananda Mohan, P.V.: Residue Number Systems: Theory and Applications. Springer, Cham (2016)
Mokbel, M.F., Aref, W.G., Kamel, I.: Performance of multi-dimensional space-filling curves. In: Proceedings of the 10th ACM International Symposium on Advances in Geographic Information Systems, pp. 149–154. ACM (2002)
Norman, M.G., Moscato, P.: The Euclidean traveling salesman problem and a space-filling curve. Chaos Solitons Fractals 6, 389–397 (1995)
Omondi, A., Premkumar, B.: Residue Number Systems: Theory and Implementation. Advances in Computer Science and Engineering: Texts, Imperial College Press, London (2007)
Pan, C.H., Liu, S.Y.: A comparative study of order batching algorithms. Omega 23(6), 691–700 (1995)
Wang, M.J., Hu, M.H., Ku, M.Y.: A solution to the unequal area facilities layout problem by genetic algorithm. Comput. Ind. 56(2), 207–220 (2005)
Whitehead, B.A., Choate, T.D.: Evolving space-filling curves to distribute radial basis functions over an input space. IEEE Trans. Neural Netw. 5(1), 15–23 (1994)
Yan, Y., Mostofi, Y.: Efficient clustering and path planning strategies for robotic data collection using space-filling curves. IEEE Trans. Contr. Netw. Syst. (99) (2016). http://ieeexplore.ieee.org/document/7480435/
Yu, Z., Jinhai, L., Guochang, G., Rubo, Z., Haiyan, Y.: An implementation of evolutionary computation for path planning of cooperative mobile robots. In: Proceedings of the 4th World Congress on Intelligent Control and Automation, 2002, vol. 3, pp. 1798–1802. IEEE (2002)
Acknowledgment
This work was supported by the Czech Science Foundation under the grant no. GJ16-25694Y and by the projects SP2017/100 “Parallel processing of Big Data IV”and SP2017/85 “Processing and advanced analysis of bio-medical data II”, of the Student Grant System, VŠB-Technical University of Ostrava.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Platoš, J., Nowaková, J., Krömer, P., Snášel, V. (2018). Space-Filling Curves based on Residue Number System. In: Barolli, L., Woungang, I., Hussain, O. (eds) Advances in Intelligent Networking and Collaborative Systems. INCoS 2017. Lecture Notes on Data Engineering and Communications Technologies, vol 8. Springer, Cham. https://doi.org/10.1007/978-3-319-65636-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-65636-6_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-65635-9
Online ISBN: 978-3-319-65636-6
eBook Packages: EngineeringEngineering (R0)