# 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

*N*− 1 segments where each segment connects two consecutive

*D*

*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