Today I Learned

Some of the things I've learned every day since Oct 10, 2016

118: Clustering in the Hilbert Curve

The Hilbert map between 1-dimensional and 2-dimensional space has the nice property that distances between points in 1D space are (relatively) preserved when those points are mapped into 2D space. Informally, if 2 points are close together on a line segment then they will also be close together when that segment is transformed into a Hilbert curve.

The converse is not always true, but is in some cases.

This property is illustrated in the picture below, which is the result of mapping the color spectrum into a square using the Hilbert mapping (image courtesy of Jason Davies):

hilbertcolors

Because of this nice locality property, the Hilbert curve lends itself to many applications in computer science. For instance, if one wants to index multi-dimensional data in a way that indices preserve the distance between datapoints, a multi-dimensional Hilbert mapping can be used. (The Hilbert curve has generalizations beyond just 2 dimensions.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: