Invited Talk
Special Topics in Computer Science
Department of Computer Science and Information Engineering
National Chung Cheng University
March 17, 2003
Hilbert Space Filling Curves: Theory and Applications
黃秋煌教授
逢甲大學資訊工程學系
Abstract
We present a tensor product formulation for Hilbert space-filling curves. Both
recursive and iterative formulas are expressed in the paper. We view a Hilbert
space-filling curve as a permutation which maps two-dimensional
$2^n \times 2^n$ data elements stored in the row major or column major order
to the order of traversing a Hilbert curve. The tensor product formula of
Hilbert space-filling curves uses several permutation operations: stride
permutation, radix-2 Gray permutation, transposition, and anti-diagonal
transposition. The iterative tensor product formula can be manipulated to
obtain the inverse Hilbert permutation. Also, the formulas are directly
translated into computer programs which can be used in various applications
including image processing, VLSI component layout, and R-tree indexing, etc.