Approximating fractal curves - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:21:51Z http://mathoverflow.net/feeds/question/98783 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98783/approximating-fractal-curves Approximating fractal curves Physics Monkey 2012-06-04T17:05:09Z 2012-06-28T05:18:16Z <p>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$?</p> <p>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.</p> <p>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.</p> <p>This is my first time posting, so my apologies if the question is too elementary.</p> http://mathoverflow.net/questions/98783/approximating-fractal-curves/100169#100169 Answer by Jim Belk for Approximating fractal curves Jim Belk 2012-06-20T19:19:00Z 2012-06-20T22:22:57Z <p>I'm certainly not an expert on this subject, but I do have a few naive suggestions.</p> <p>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.</p> <p>Therefore, one possible approach would be the following:</p> <ol> <li><p>Choose a continuous function $F(x,y)$ on the square whose zero set is the given fractal.</p></li> <li><p>Find the Fourier sum $f$ which best approximates the function $F$.</p></li> </ol> <p>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.</p> <p>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.</p> <p>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.</p> <p><strong>Edit:</strong> I tried this in <em>Mathematica</em>, and it seems to work. Here is a plot of the zero set for a Fourier series with $N=50$:</p> <p><img src="http://i45.tinypic.com/33aqxs0.jpg" alt="alt text"></p> <p>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.</p> http://mathoverflow.net/questions/98783/approximating-fractal-curves/100841#100841 Answer by Kyle Kinneberg for Approximating fractal curves Kyle Kinneberg 2012-06-28T05:18:16Z 2012-06-28T05:18:16Z <p>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). </p> <p>Pilgrim, in <a href="http://arxiv.org/pdf/math/9905170v1.pdf" rel="nofollow">Dessins d'enfants and Hubbard trees</a>, 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$. </p> <p>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!).</p>