On p-Norm Based Locality Measures of Space-Filling Curves

摘要

A discrete space-filling curve provides a linear indexing or traversal of a multi-dimensional grid space. We present an analytical study on the locality properties of the 2-dimensional Hilbert curve family. The underlying locality measure, based on the p-normed metric d_p, is the maximum ratio of d_p (υ, u)~m to d_p (υ, u) over all corresponding point-pairs (υ,u) and (υ,u) in the m-dimensional grid space and (1-dimensional) index space, respectively. Our analytical results close the gaps between the current best lower and upper bounds with exact formulas for p ∈ {1, 2}, and extend to all reals p ≥ 2.