I've posted images of the fractal that solves this problem here: http://milou.msc.cornell.edu/images/ The sequence shows a greek cross being iteratively refined, with successive crosses rotated by 45 degrees. Each one is connected, and it looks like there is no pinch-off in the limit either. Each one of these shapes tiles the plane with square lattice translations, and in two ways. The two sets of translations (square lattices) are related by a rotation that approaches 45 degrees in the limit. Here's how you use these shapes to solve the optimization problem, an optimal matching. Center the shape on any point of one of the square lattices; it will contain exactly one point of the other lattice because it is a fundamental domain of that lattice. This also works the other way, and the correspondence of points of the two lattices is symmetric because the shape is a fundamental domain of both lattices and has central symmetry. There are many fractal shapes that serve as fundamental domains to both lattices, but this one is special because it has the smallest second moment (quantization error). Veit On Jul 31, 2011, at 2:14 PM, Veit Elser wrote:

The Mandelbrot posts reminded me of something:

Are fractal sets ever the solution of an optimization problem?

Here's one instance I discovered a couple of years ago:

Take an infinite square grid of red points and an identical grid of blue points. Now take the blue grid and rotate it by 45 degrees with respect to the red grid. The problem is to form a perfect matching of red and blue points such that the matching minimizes the sum of the squared distances between pairs.

If the infinite value of the thing being minimized bothers you, do this: Use a continued fraction approximation for sqrt(2) to approximate the blue grid so that it becomes commensurate with the red grid (at periods that increase with the order of the continued fraction approximation). Now solve the optimization problem on just one (finite) period. To get the fractal, translate all the matched (red, blue) pairs so the red point is at the origin, and observe how the set of blue points evolves with order of approximation.

Veit _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun