Hilbert Sort

This page covers an algorithm for implementing a Hilbert Sort, which sorts points according to the order in which they would be visited by a fractal, space-filing curve called the Hilbert Curve.

Background

Problem Setup and Motivation

Consider a problem in which we are trying to store/pack up spatial data in an efficient way. We need a way of sorting the data in such a way that (x,y) data that are located in nearby regions to one another will live closer in memory to one another. This speeds up access to the data in memory.

If we sort by, say, x-coordinates, and let y-coordinates break ties, then we end up with points with very similar x values but dissimilar y values. These are inefficient and spread out the points in memory. (x,y) data points that are far away in space end up being neighbors in memory, and vice-versa.

Using Euclidean distance is another possible approach, but this does not utilize direction, and so you can again end up with points that are similar distances from a reference point, but in opposite directions, leading to data points that are far away in space becoming neighbors in memory.

If we imagine this problem getting much larger - for example, if the set of (x,y) data points becomes millions of points on a map - the Hilbert sort provides a way to pack up data in a way that preserves local, spatial structure. The closer two given points are in memory, the shorter the interval time between visits by the space-filling curve.

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 a new curve in a paper published in 1890, subsequently called the Hilbert curve.

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 constructed a curve by bending a line at two points. Starting with this simple shape, the curve is shrunk by a factor of 2, and repeated four times. Two of the curves are rotated, and each of the four curves are connected together.

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.

Problem Statement

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

A few keys to successfully solving the Hilbert Curve problem:

• The motive for the Hilbert Curve is that data is grouped by how close it is spatially; if a point is in the lower left quadrant, it will always be visited before another point in the upper right quadrant. This means that all points in the lower left quadrant will always be visited before all points in the upper right quadrant.
• The rotation is the tricky part of the problem, mainly because when we rotate the curve, we use the rotated version of the curve as the starting point for any additional calls in that quadrant. So, the rotations have to recurse with us.
• The curves are not simply rotated 90 degrees, the curves are actually flipped and rotated about a diagonal axis (going from one corner to another). This affects subsequent rotations.

Implementation Strategy

The implementation strategy is, obviously, recursive. What we want to do at each level is:

• Start with the Hilbert curve contained in a square.
• Cut the square under consideration into four quadrants.
• Apply a transformation to each square so that it is re-oriented in a manner that matches our original Hilbert curve.
• Once each of those squares goes through all of its respective recursive calls, it will return a sorted list of points. Then we will know what to do - we collect each of the sorted points from each of the four quadrants in order, maintain that order, and return those sorted quadrants.

To nail down the details, treat the square under consideration as ranging from (0,0) to (S,S).

• Each time we cut a square into quadrants, we re-orient ourselves as to where (0,0) is located and which quadrants will be visited in which order.
• If we are in the lower left quadrant, x is below S/2 and y is below S/2, so we rotate and reflect by swapping x and y.
  • X -> Y
  • Y -> X
• If we are in the upper left quadrant, x is below S/2, y is above S/2, so subtract S/2 from y and we're done
  • X -> X
  • Y -> Y-(S/2)
• If we are in the upper right quadrant, x is above S/2, y is above S/2, so subtract S/2 from both
  • X -> X - S/2
  • Y -> Y - S/2
• If we are in the lower right quadrant, our x and y values are now relative to the quadrant bounding box. The distance to the top of the bounding box to the y coordinate becomes our new x coordinate, while the distance from the right of the bounding box S to the x coordinate becomes our new y coordinate:
  • X -> S/2 - Y
  • Y -> S - X

Recursion always requires a base case and a recursive case. 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.

Bookkeeping

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) quadrants of subsequent quadrants, instead we can just transform each (x,y) point so that the order in which the (correct, transformed) Hilbert curve would visit them is preserved as the order in which the (now transformed back to its original shape) Hilbert curve would visit them.