#### Title

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;

#### Date of this Version

2008

## Comments

Encyclopedia of GIS, 2008, Part 22, 1068-1072