Approximating fractal curves - MathOverflow

Approximating fractal curves

2012-06-04T17:05:09Z

Is there a known algorithm for approximating a fractal curve, say as specified by some iterative procedure e.g. a Koch snowflake, in terms of $f^{-1}(0)$ for some "simple" function $f$?

Specifically, consider the set $\mathcal{F} = \{(x,y)|f(x,y) = 0 \}$ where $f(x,y) = \sum_{n,m=-N}^N t_{nm} e^{i n x + i m y}$ and $f$ is real. I would like a procedure to determine the parameters $t_{nm}$ such that the set $\mathcal{F}$ is close to the actual fractal curve. Presumably the number $N$ will grow as the required error decreases.

I have been trying to approach this problem by truncating the iteration procedure for the fractal and approximating that piecewise linear curve, but I realized that I don't know a good way to do this either.

This is my first time posting, so my apologies if the question is too elementary.

Answer by Jim Belk for Approximating fractal curves

2012-06-20T19:19:00Z

I'm certainly not an expert on this subject, but I do have a few naive suggestions.

The function $f(x,y) = \sum_{n,m=-N}^N t_{mn}e^{inx+imy}$ is just a finite Fourier sum defined on a square. It is well-known how to find a finite Fourier sum that "best" approximates a given continuous function on a square.

Therefore, one possible approach would be the following:

Choose a continuous function $F(x,y)$ on the square whose zero set is the given fractal.
Find the Fourier sum $f$ which best approximates the function $F$.

For step (1), one potential choice would be to use standard distance function to a compact set, i.e. $$ F(p) \;=\; \min\{ d(p,q) \mid q\in\text{the fractal set} \} $$ where $d$ denotes Euclidean distance in the plane. The problem with this choice is that, if you perturb the function $F$ slightly, the zero set might disappear entirely.

It would be better to start with a continuous function $F$ whose graph intersects the $xy$-plane transversely along the fractal curve. For something like the the Koch snowflake, you could use a continuous function $F$ which is positive outside of the snowflake and negative inside, e.g. use the distance function for the outside and the negative of the distance function on the inside.

Also, practically speaking, there's no reason why the function $F$ really needs to be continuous. For example, if you start with a piecewise function $F$ which is $1$ outside of the Koch snowflake and $-1$ inside the Koch snowflake, then the Fourier approximations for $F$ might work fairly well.

Edit: I tried this in Mathematica, and it seems to work. Here is a plot of the zero set for a Fourier series with $N=50$:

For $F$, I used a function which is $1$ outside the third iterate for the Koch snowflake, and $-1$ inside. I used Green's Theorem to compute the double integrals for the coefficients.

Answer by Kyle Kinneberg for Approximating fractal curves

2012-06-28T05:18:16Z

I don't think this is much related to your specific question, but it does have to do with the general question of approximating fractal curves (and I just came across it this week).

Pilgrim, in Dessins d'enfants and Hubbard trees, studies certain types of Belyi polynomials whose iterates give a dynamical system that can be described by some nice combinatorics, namely the dessins of the iterates. He makes a remark at the end of page 13 that the dessins of $f^{\circ n}$ (so the pre-image of the interval $[0,1]$ by the $n$-th iterate of $f$, where $f$ is an "extra clean dynamical Belyi polynomial" on $\mathbb{C}$) converge exponentially fast to the Julia set of $f$.

Of course, the sorts of fractals that arise as Julia sets in this way is pretty limited, but I still think it's a nice example for your general question. Especially considering that the approximating objects are so simple (even a child could draw them!).