Hilbert Sort

Problem Description

Consider a set of (x,y) points that we would like to have access to, as quickly as possible.

A first pass approach might be: sort the points according to their x-coordinate values.

However, this method of sorting the points is not optimal: two points with nearby x values may still be on opposite sides of the grid.

Another approach is to sort points according to Euclidean distance, so that the nearness of points becomes a function of the coordinate values x and y.

More generally, we can preserve distances between points by sorting points along a space-filling curve.

(More information is needed here.)

Space Filling Curves

Space filling curves are curves that are capable of "filling up" a finite area with longer and longer distances.

We can think of space-filling curves as being parameterized on a numerical parameter that controls the amount of curvature or the degree of "packing" of the curve.

The way that space-filling curves are constructed is to create a pattern, then scale it down and repeat it, attaching the subsequent scaled-down, repeated curves.

Mathematician Giuseppe Peano was the first to discover the space filling curves. His Peano curve is an example of a triplet curve that is scaled down by 1/3 on both sides and repeated 9 times.

David Hilbert then expanded on the idea with his Hilbert Curve in a paper published in 1890.

Hilbert Curve

The Hilbert Curve is a particular space-filling curve invented by David Hilbert, a famous mathematician who lived around the turn of the 20th century and is recognized as a universally influential mathematician.

Hilbert proposed the construction of a space-filling curve based on bending a line at two additional points. By starting with a squared-off U shape, the curve is repeated by shrinking it in half on both sides, and repeating it 4 times, connecting each of the four curves.

The Hilbert Curve can be drawn in a region bounded by the four points (0,0), (0,S), (S,0), (S,S). Construct it by splitting the square into four quadrants meeting at (S/2, S/2). Recursively fill them with a rotated and scaled copy of the curve.

Given (x,y) coordinate locations, sort them according to when the Hilbert Curve visits them. If the number of nodes on the grid, S, is odd, then the curve will not intersect itself and each integer point will only be visited once.

Solution Approach

The Hilbert Curve sort problem can be solved by observing a simple fact: the coarsest level of quadrant organization takes precedence over finer grained levels of quadrant organization. So, if one point is in the southwest corner and one point ins in the northeast corner, then no matter what iteration it takes for the Hilbert Curve to visit those two points, we definitely know that the curve will visit the southwest corner before it visits the northeast corner.

This begins to take on the characteristics of a recursive method: our "base case" is the simple comparison of one or no points in each of our four quadrants. If we get to this base case, we know the order in which the Hilbert Curve will visit each of those points.

If we are not at the base case, if we have a large number of points to sort, we can bin together all the points in a given quadrant, and consider the order in which those points go with an additional level of finer granularity.

Implementation Details

The biggest challenge to implementing this is dealing with the rotation of the curve for the southwest and southeast corners.

There are a couple of ways to handle the rotation - there's a messy conditional approach, and a more elegant approach that transforms the (x,y) data in a bin, rather than trying to transform the bin to fit the (x,y) data.

Conditional Approach

The first way is to look at two different levels when binning points into quadrants; that allows you to say, "if point A is in the southeast quadrant on this level, and was in the southwest quadrant on the prior level, then it should go second, but if it was in the northwest quadrant on the prior level, then it should go fourth, etc."

This is clunky and awkward to code, and you wind up with a bunch of nested if/else statements.

Transform the Data, Not the Bin

The second way is to say, okay, when we bin these (x,y) points into their respective quadrants, the only thing we care about is what order they're visited by the Hilbert Curve, and that only depends on what quadrant they're in, so we can actually change the (x,y) values to be anything we want - as long as we don't change the order in which they would be visited by the Hilbert curve. Which is to say, which quadrants they're in.

This technique can be thought of as transforming the (x,y) data associated with each point to fit the bin structure, rather than transforming the bin structure to fit the (x,y) data.

For example, the southwest corner is always inverted and rotated 90 degrees. So rather than trying to account for that inversion and rotation when looking at the (southwest, northwest, northeast, and southeast