On Wed, Sep 10, 2008 at 3:14 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
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)
The RHS of each of these should have a (x,y) -> at their beginning.
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]?
Sorry, I wasn't very clear at all. Let me start over. Take a finite set of contractive transformations T. Then there is an unique compact set A_T such that A_T = union_i T_i(A_T). Call it "T's attractor". For example, for T = {x -> 1/4x + i/4, i = 0 .. 3}, A_T = [0,1]. For T = {(x,y) -> 1/2 (x,y) + 1/2(i,j), i = 0 .. 1, j = 0 .. 1}, A_T = [0,1] x [0,1]. Here's another way to think of A_T: Take an infinite sequence of transformations, each chosen from T, and compose them all in order. The resulting transformation will be of the form x -> p for some p in A_T. Call the infinite sequence of transformations that results in x -> p "an address for p". A point can have multiple addresses and in fact unless A_T is a Cantor set, some point in A_T will have multiple addresses. Perhaps the most familiar example of multiple addresses is when T = {x -> 1/10 x + i/10, i = 0 .. 9}, then if we let i stand for T_i we have 0 o 9 o 9 o 9 o ... = 1 o 0 o 0 o 0 o ... (where I'm using "o" as the composition operator) because both are addresses for 0.1. We are now ready to talk about morphisms between fractals. F:T -> S is simply a mapping between the finite sets T and S with the additional requirement that it preserves any address overlaps from T: if t_1 o t_2 o t_3 o ... = t_1' o t_2' o t_3' o ... for t_i and t_i in T, then F(t_1) o F(t_2) o F(t_3) o ... = F(t_1') o F(t_2') o F(t_3') o ...
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.]
Yes. I believe that any fractal morphism from T_d = {x -> 1/d x + i/d, i = 0 .. d-1 } to a fractal cube will support this sort of indexing. Given a point in [0,1], simply take its address (i.e., its base d expansion) to the desired accuracy, then translate this address prefix with F to get the sub-cube address prefix. The only slight complication is that each transformation of the fractal cube will look something like x -> 1/2 R(x) + 1/2 j where j is a vector with 0/1 entries and R is a symmetry of the cube, so you'll have to compose the various R's after you translate. The inverse mapping works similarly, except that you'll have to tile the region of the cube you want mapped with subcubes. -Thomas C
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun