Governance by those who do the work.

Sunday, April 6, 2014

Recurrence for Multidimensional Space-Filling Functions

"Recurrence for Multidimensional Space-Filling Functions" is the culmination of many years' interest in space-filling curves and functions.  The recurrences result from a de novo analysis that was more engineering than mathematical.  Instead of trying to characterize all possible curves or base patterns, I focused on finding a cell algorithm for all ranks and side lengths (greater than 2) and making that work with a self-similar recurrence subject to scaling laws I discovered from previous implementations.

That cell algorithm is "serpentine".  It turns out that both the Peano and Hilbert (multidimensional) space-filling curves are instances of my recurrence working on serpentine patterns.

From there I generalized the alignment function.  In the alignment function there were degrees of freedom for diagonal-corner cells (with odd side lengths) which were easy to employ to improve their isotropy (Peano curves are anisotropic).  There are degrees of freedom for adjacent-corner cells of rank greater than 2, but deeper analysis will be required to understand them.

While the alignment function seems to work for all serpentine cells (I verified thousands of combinations of rank and side-length), this is not yet proven.  And Figure 20 at the end of the paper shows a non-serpentine 3x3x3 adjacent-corner cell whose symmetrical version works with my alignment function, but whose asymmetrical variant does not.  Future explorations should determine if that asymmetrical cell itself is valid, and discover the constraint on cells if that is not the case.

The non-terminating recurrence is elegant but was tricky to discover because its truncated form returns coordinates at the center of sub-cells rather than at their origins as the integer recurrence does.

The centered form was accomplished by generalizing the offsets I earlier discovered for centering the Peano curve.

No comments: