Abstract
This paper presents bounds on the quality of partitions induced by space-filling curves. We compare the surface that surrounds an arbitrary index range with the optimal partition in the grid, i. e. the square. It is shown that partitions induced by Lebesgue and Hilbert curves behave about 1.85 times worse with respect to the length of the surface. The Lebesgue indexing gives better results than the Hilbert indexing in worst case analysis. Furthermore, the surface of partitions based on the Lebesgue indexing are at most \( \frac{5} {{2 \cdot \sqrt 3 }} \) times larger than the optimal in average case.
Chapter PDF
Similar content being viewed by others
References
P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, 1998.
T. Asano, D. Ranjan, T. Roos, E. Welzl, and P. Widmayer. Space-filling curves and their use in the design of geometric data structures. Theoretical Computer Science, 181:3–15, 1997.
J. Behrens and J. Zimmermann. Parallelizing an unstructured grid generator with a space-filling curve approach. In A. Bode, T. Ludwig, W. Karl, and R. Wismüller, editors, Euro-Par 2000, LNCS 1900, pages 815–823. Springer, 2000.
S. Craver, B.-L. Yeo, and M. Yeung. Multilinearization data structure for image browsing. In SPIE-The International Society for Optical Engineering, pages 155-, 1998.
R. Diekmann, J. Hungershöfer, M. Lux, L. Taenzer, and J.-M. Wierum. Using space filling curves for efficient contact searching. In Proc. IMACS, 2000.
C. Gotsman and M. Lindenbaum. On the metric properties of discrete space-filling curves. IEEE Transactions on Image Processing, 5(5):794–797, May 1996.
M. Griebel and G. Zumbusch. Parallel multigrid in an adaptive PDE solver based on hashing and space-filling curves. Parallel Computing, 25:827–843, 1999.
B. Moon, H. V. Jagadish, C. Faloutsos, and J. H. Saltz. Analysis of the clustering properties of the Hilbert space-filling curve. IEEE Transaction on Knowledge and Data Engineering, 13(1), Jan/Feb 2001.
R. Niedermeier, K. Reinhardt, and P. Sanders. Towards optimal locality in mesh-indexings. LNCS 1279, 1997.
R. Pajarola and P. Widmayer. An image compression method for spatial search. IEEE Transactions on Image Processing, 9(3):357–365, 2000.
H. Sagan. Space Filling Curves. Springer, 1994.
S.-H. Teng. Provably good partitioning and load balancing algorithms for parallel adaptive N-body simulation. SIAM Journal on Scientific Computing, 19(2):635–656, 1998.
J.-M. Wierum. Average case quality of partitions induced by the Lebesgue indexing. Technical Report TR-002-01, Paderborn Center for Parallel Computing, http://www.upb.de/pc2/, 2001.
G. Zumbusch. On the quality of space-filling curve induced partitions. Zeitschrift für Angewandte Mathematik und Mechanik, 81, SUPP/1:25–28, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hungershöfer, J., Wierum, JM. (2002). On the Quality of Partitions Based on Space-Filling Curves. In: Sloot, P.M.A., Hoekstra, A.G., Tan, C.J.K., Dongarra, J.J. (eds) Computational Science — ICCS 2002. ICCS 2002. Lecture Notes in Computer Science, vol 2331. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47789-6_4
Download citation
DOI: https://doi.org/10.1007/3-540-47789-6_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43594-5
Online ISBN: 978-3-540-47789-1
eBook Packages: Springer Book Archive