Performance of multi-dimensional space-filling curves
Mohamed F. Mokbel, Walid G. Aref, Ibrahim Kamel · 2002
A space-filling CurV(l is a way of mapping the multi-dimensional space into the one-dimensional space.It acts like a thread that passes through every cdl clement (or pixel) in the V-dimensional Space so that every C:(lll is visited exactly once.There are numerous kinds of space-filling curves.The difference between such curves is in their way of mapping to the one-dimensional space.Selecting the appropriate curve for any application requires knowledge of the mapping schcme provided by each space-filling curve.A space-filling curve consists of a set of segments.Each segment connects two consecutive multi-ilimensional points.Five different t.ypes of segments are distinguished, namely, .Jump, Contiguity, Reverse, Forward, and Still.A dcscription vector V = (.J,C,R,F,S), where.J, 0, R, P, and 5, arc the percentages of .Jump, Contiguity, Rcvcrse, FOlllJUf"d, and Still segments in the space-filling curve, encapsulates all the properties of a space-filling curve.The knowledgc of \I facilitates the process of selecting the appropriate space-filling curve for different applications.Closed formulas are developed to compute the description vector \I for any D-dimensional space and grid size N for different space-filling curves.A comparative study of cliIferent space-filling curV(!S with respect to the description vcctor is conclucted and rcsults are presented and diSCllssed.