# Shortest Paths on fractals

How can one find shortest paths between 2 specified points on fractals, or (since I'm pretty sure this is quite complicated) make useful generalizations about them?

Since the above question is broad, how about this one: What is the general formulation (in a direct equation, recursive formulation, or other form) for distance between 2 points on the sierpinski carpet?

Obviously for some fractals all points are infinite. Identifying these is often easy, but are there any edge cases where it's hard to decide whether all paths are infinite length? And if so, how does one decide?

Edit: This question was inspired, by the way, by this thread on a different website (where it became clear that it was beyond the average math knowledge there). http://echochamber.me/viewtopic.php?f=3&t=40348#p1618494 That particular post shows paths(whose presence is recursive) in the carpet.

-
You might be interested in this paper which discusses an application of shortest paths on the Sierpiński graphs, ie. the finite graphs approximating the Sierpiński gadget. –  Dan Piponi May 25 '10 at 16:49

As to the border case. An example that you might like to consider is given by the blanc-mange curve, $f_{\lambda}:\mathbb{R}\to\mathbb{R}$, that for any value of $0\leq\lambda\leq 1,$ is defined as the unique bounded solution of the fixed point functional equation

$f(x)=\mathrm{dist }(x,\mathbb{Z})+\lambda f(2x)$

(by the contraction principle there is a unique such function; it is continuous and 1-periodic, with an immediate series expansion coming from the iteration).

Consider $f_{\lambda}$ on the unit interval. If you take $\lambda=1/4$ you find a parabola; with $\lambda < 1/2$ it's Lipschitz (hence the graph has a finite length) with constant $(1-2\lambda)^{-1}$; if $\lambda > 1/2$ it's Hoelder continuous with an exponent depending from $\lambda$. The parameter 1/2 is critical: you find a curve that is not Lipschitz, but it's Hoelder of all exponents $\alpha>0$, precisely, it has a modulus of continuity ct|log(t)|, and looking at it a bit more closely, it is not of bounded variation on any nontrivial interval (so the graph is not rectifiable even locally), nor is BV for any $\lambda \geq 1/2.$

-
As to the geodesic distance in the Sierpiński carpet S. A nice problem there is! Though it seems difficult. The geodesic distance function d(x,y) should satisfy a functional equation due to the self-similarity of S. But I don't see enough information to identify it. Note that two opposite corners (0,0) and (1,1) may be connected easily because the straight segments from (0,0) to (0,1/2) and from (0,1/2) to (1,1) are completely included in S. This make a length 2sqrt(5)/3 that in this case is clearly minimal. I imagine that S contain a dense set of line-segments, indeed. –  Pietro Majer May 25 '10 at 14:51

For the Sierpinski carpet, using the metric induced by its embedding in $\mathbb{R}^2$ is quite difficult computationally. There are alternative metrics: for fractals arising from hyperbolic iterated function systems (of which the Sierpinski carpet is one), one can identify points via its tops code space, which involves determining which subcopies of the Sierpinski carpet a point lies in. It's not difficult to place a metric on the tops code space of such a fractal, and this in some sense tells us how "close" two points are, in terms of how many iterations of the function system have to occur before the two points are sent to different subcopies of the fractal. It's a bit difficult to make this more precise without going into a fair bit of detail; I'm pretty sure this is all covered in Michael Barnsley's textbook Fractals Everywhere though. Note also of course that this only works for fractals arising from hyperbolic iterated function systems, which includes other fractals like the Koch curve and the Menger sponge.

-