Space-Filling Curves
Abstract
A space-filling curve (SFC) is a way of mapping a multi-dimensional space into a one-dimensional space. It acts like a thread that passes through every cell element (or pixel) in the multi-dimensional space so that every cell is visited exactly once. Thus, a space-filling curve imposes a linear order of points in the multi-dimensional space. A D
-dimensional space-filling curve in a space of N cells (pixels) of each dimension consists of ND − 1 segments where each segment connects two consecutive D
-dimensional points. There are numerous kinds of space filling curves (e. g., Hilbert, Peano, and Gray). The difference between such curves is in their way of mapping to the one-dimensional space, i. e., the order that a certain space-filling curve traverses the multi-dimensional space. The quality of a space-filling curve is measured by its ability to preserve the locality (or relative distance) of multi-dimensional points in the mapped one-dimensional space. The main idea is that any two D -dimensional points that are close by in the D
-dimensional space should be also close by in the one-dimensional space.
Keywords
Distance-preserving mapping, Locality-preserving mapping, Multi-dimensional mapping, Linearization
Date of this Version
2008
Comments
Encyclopedia of GIS 2008, Part 22, 1068-1072