On 9/8/08, Thomas Colthurst <thomaswc@gmail.com> wrote:
I have a slightly idiosyncratic take on Hilbert curves which may be of interest.
Specifically, I think of them of morphisms from fractal lines to fractal cubes.
For example, I think of the original 2d Hilbert curve as the morphism F such that F(x -> 1/4x) = 1/2 (y,x) F(x -> 1/4x + 1/4) = 1/2 (x,y) + (0,1/2) F(x -> 1/4x + 2/4) = 1/2 (x,y) + (1/2,1/2) F(x -> 1/4x + 3/4) = 1/2 (1-y,x) + (1/2,0)
What makes it a morphism is that it preserves relations between "addresses" in the source fractal's attractor. For example, if we denote x -> 1/4 x + j/4 by j, then 0(3(3(3(3(...))))) = 1(0(0(0(0(...))))) and F0(F3(F3(F3(...)))) = F1(F0(F0(F0(...))))
Such a morphism on transformations then induces a continuous mapping on the geometric fractals (the attractors of the transformations, to use Iterated Function System lingo). ...
Presumably "morphism" means function(al) transforming (geometric) mappings, but with some extra constraint: along the lines of F(g(f)) = g(F(f)), for g in some (other) class of mappings perhaps? But I'm still confused: is "x" on the LHS above the same as on the RHS --- in which case, where did "y" spring from? Or should there be some other variable t on the LHS, with (implicitly) forward and reverse mappings from t to [x,y]?
What makes it a morphism is that it preserves relations between "addresses" in the source fractal's attractor. For example, if we denote x -> 1/4 x + j/4 by j, then 0(3(3(3(3(...))))) = 1(0(0(0(0(...))))) and F0(F3(F3(F3(...)))) = F1(F0(F0(F0(...))))
This certainly looks intriguing; but I must request more explanation, please! ---------------------------------------- Or I could take the initiative, and instead ask: does your paradigm cast any light on the "indexing" problem: to develop algorithms which approximately evaluate the d-space coordinate vector along the Hilbert curve as a function of the 1-space enumeration variable, together with the inverse function, in (amortised) time logarithmic in the length of any subinterval to which the variable is restricted? [Since the inverse function is discontinuous, this ambition may require modification to become practicable.] The efficient indexing point of view --- discretely, at any rate --- can be profitably be taken of other combinatorial problems besides Hilbert walk: permutations and combinations etc, and Tower of Hanoi and its derivatives come at once to mind. In the classical ToH for example, so beloved of elementary computer programming instructors, this approach uncovers an unexpected constant-time algorithm for enumeration, along with a mapping from legal configurations to consecutive natural numbers which improves the storage requirements of tree-searching computations involving ToH. On another note, it's claimed in a couple of internet articles that the Hilbert curve is "self-intersecting" (by somebody-or-other's theorem). Presumably what they mean is that it touches itself (which it obviously does, at any point with finite binary coordinates) rather than crossing itself (which it obviously does not). Can anybody out there elucidate? Fred Lunnon