Title :
On the metric properties of discrete space-filling curves
Author :
Gotsman, C. ; Lindenbaum, M.
Author_Institution :
Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel
Abstract :
Discrete space-filling curves are commonly used to reduce a multidimensional problem to a one-dimensional problem, and, as such, are exploited in a variety of image processing applications. The space-filling curve is essentially a linear traversal of the discrete multidimensional space. In order that this traversal be effective, the curve should preserve “locality”, namely, that points close in the original multidimensional space be close in their ordering along the curve, and vice versa. We quantify “locality” and provide upper and lower bounds on the locality of multidimensional space-filling curves. We also bound the locality of the classic Hilbert space-filling curves, showing that they come close to achieving optimal locality
Keywords :
Hilbert spaces; Hilbert space; discrete multidimensional space; discrete space-filling curves; image processing; locality; lower bounds; upper bounds; Application software; Computer science; Data compression; Euclidean distance; Filling; Hilbert space; Image processing; Multidimensional systems; Q measurement; Quantization;
Conference_Titel :
Pattern Recognition, 1994. Vol. 3 - Conference C: Signal Processing, Proceedings of the 12th IAPR International Conference on
Conference_Location :
Jerusalem
Print_ISBN :
0-8186-6275-1
DOI :
10.1109/ICPR.1994.577130