On the metric properties of discrete space-filling curves
On the metric properties of discrete space-filling curves
复制标题
DOI：
10.1109/icpr.1994.577130
复制
发表时间：
1994-10
期刊：
影响因子：
--
通讯作者：
C. Gotsman;M. Lindenbaum
中科院分区：
文献类型：
--
作者：
C. Gotsman;M. Lindenbaum
离散空间填充曲线通常用于将多维问题简化为一维问题，因此在各种图像处理应用中都被利用。空间填充曲线本质上是离散多维空间的线性遍历。为了使这种遍历有效，曲线应该保持“局部性”，即在原始多维空间中接近的点在它们沿曲线的顺序上是接近的，反之亦然。我们量化了“局部性”，并给出了多维空间填充曲线局部性的上下界。我们还限定了经典的Hilbert空间填充曲线的局部性，表明它们接近于达到最优局部性。
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.