2007-05-11, 06:05
This is quickfur's alter ego (I forgot my password and forgot which of my many email addresses I used to sign up 
).
Anyway, I was experimenting with iterated algorithms and stumbled across the following observation, which led me to conjecture that perhaps it's generalizable to n-dimensions, and possibly to any kind of tiling of n-space. However, I'm not clear how to rigorously define my conjecture, so I'm posting here to see what people say.
First, let me explain the "intuitive" motivation behind the following definitions. The idea is that I have a grid of squares, each of which is associated with a scalar value. Initially, only one square has a non-zero positive value, which can be any value but we might as well define it to be 1. You may think of this as a "drop of liquid". At every unit time thereafter, this "liquid" spreads to adjacent squares. Since there are 4 squares surrounding each square, the liquid spreads into 5 equal parts, one on the square it is on, and the others added to the neighbouring squares. We proceed this way, and after N iterations, we look at all squares with a value greater than H, for some positive H. such that H is less than the maximum value of all squares, and greater than some threshold (which I'm not sure how to define). The set of squares included will be a pixelated approximation to a circle---at least, this is what I think, I'm not sure how to prove it.
Anyway, enough hand-waving. Let's be more precise: let)
represent the value of the square (or n-cube) at coordinate 
at time 
. Let 
be the set of orthogonal unit basis vectors for 
. Let 
, where 
represents the zero vector. Then 
is defined recursively by:
 = 1\\<br />
F(0,\vec{v}) = 0\ \mbox{where \vec{v} \neq \vec{0}}\\<br />
F(t,\vec{v}) = \sum_{\vec{b}\in B^*} \frac{F(t-1,\ \vec{v} + \vec{b})}{||B^*||}<br />
)
Each value of represents the next iteration of the "spreading" of the "liquid" over the square (n-cubical) grid of . Let  > k\})
. The claim is that for large values of 
and certain values of ))
, 
approximates an n-ball. (Well, I've only actually tested this for n=2, a circular disk.
Unresolved issues:
* I am almost certain that my claim is true for n=2. I wrote a Perl script to actually compute iteratively, and the results indeed do look like concentric circles (if you map each square to a pixel). However, I don't know how to prove this. It must involve taking some limit on N, but I don't know how to formulate it so that the circle doesn't become infinitely large.
* I am less sure of higher dimensions, since I don't have a convenient way to check this for significantly large values of N. (How to visually check this??) So we will need actual mathematical proof here.
* I highly suspect that if the claim is indeed true, then this phenomenon cannot possibly occur only for a square grid; it must occur for all possible tilings of n-space (e.g., triangles, hexagons, with analogous "liquid spreading" functions). But I have no idea how to prove this.
So, can anyone help me prove or refute my conjecture?
I think one very interesting application of this conjecture, if it is true, is that it can be used to approximate the spread of liquid in a grid-based game. If you select a different initial state (not just a single non-zero square), the feedback mechanism of can produce very interesting shapes, which approximate complex shapes, but completely "pixelated" to fit in the grid, and quite easy to implement iteratively.
).Anyway, I was experimenting with iterated algorithms and stumbled across the following observation, which led me to conjecture that perhaps it's generalizable to n-dimensions, and possibly to any kind of tiling of n-space. However, I'm not clear how to rigorously define my conjecture, so I'm posting here to see what people say.
First, let me explain the "intuitive" motivation behind the following definitions. The idea is that I have a grid of squares, each of which is associated with a scalar value. Initially, only one square has a non-zero positive value, which can be any value but we might as well define it to be 1. You may think of this as a "drop of liquid". At every unit time thereafter, this "liquid" spreads to adjacent squares. Since there are 4 squares surrounding each square, the liquid spreads into 5 equal parts, one on the square it is on, and the others added to the neighbouring squares. We proceed this way, and after N iterations, we look at all squares with a value greater than H, for some positive H. such that H is less than the maximum value of all squares, and greater than some threshold (which I'm not sure how to define). The set of squares included will be a pixelated approximation to a circle---at least, this is what I think, I'm not sure how to prove it.
Anyway, enough hand-waving. Let's be more precise: let
Each value of
Unresolved issues:
* I am almost certain that my claim is true for n=2. I wrote a Perl script to actually compute
* I am less sure of higher dimensions, since I don't have a convenient way to check this for significantly large values of N. (How to visually check this??) So we will need actual mathematical proof here.
* I highly suspect that if the claim is indeed true, then this phenomenon cannot possibly occur only for a square grid; it must occur for all possible tilings of n-space (e.g., triangles, hexagons, with analogous "liquid spreading" functions). But I have no idea how to prove this.
So, can anyone help me prove or refute my conjecture?
I think one very interesting application of this conjecture, if it is true, is that it can be used to approximate the spread of liquid in a grid-based game. If you select a different initial state (not just a single non-zero square), the feedback mechanism of
. Can you provide the distribution for say n=20 or so (with colors indicating the values!)?).