I am going to try to keep this current. Today is 6-16-12.
A new web page on "statistical geometry" by Dr. Goulu has appeared at http://drgoulu.com/2011/10/03/pavages-aleatoires/. His description is "random tilings". He has apparently created some of his own new images based on the algorithm. He offers this historical view of tilings.
Depuis le XVème siècle, 17 types de pavages réguliers différents sont utilisés dans les décorations de l’Alhambra. En 1891, le mathématicien russe Evgraf Fedorov démontre que le nombre de pavages réguliers distincts vaut … 17 [1]. Et ce n’est qu’entre 1968 et 1984 qu’on parvient à classifier toutes les formes de pavés possibles en 19 catégories [2]. Depuis, les carreleurs ne peuvent se distinguer que par des motifs et des couleurs, plus par la géométrie.
En 1974, le pavage quasi-périodique de Penrose crée un choc : il est possible de recouvrir le plan avec des pavés de deux formes différentes arrangés selon des règles rigoureuses, mais ne générant pas de motif périodique. En 1994, Radin et Conway en proposent un autre, le « Pinwheel tiling ». Voilà pour le XXème siècle.
En 2011, c’est John Shier, un « artiste algorithmique » qui vient d’ouvrir tout grand la porte à une infinité de nouveaux pavages. Sa méthode permettent de couvrir le plan avec des pavés de presque n’importe quelles formes, mais de surface décroissantes [3,4]. Le principe semble tout simple : on place le plus grand pavé au hasard, puis le suivant en taille au hasard dans une surface libre et ainsi de suite.
Several items touched upon here are treated in more detail in other links within the list.
The "maximum conjecture". What is the strongest statment one can make about the algorithm which is not contradicted by computational evidence?
> The algorithm can fractalize any sequence of "reasonably compact" shapes which have the required area sequence.
What "reasonably compact" means remains to be discovered. Congruency of the shapes is apparently not important (but it simplifies computation).
Shapes which work. To date no shape which has been tried has failed to fractalize. Examples include circles, squares, rectangles, rings, crescents, and most other geometric shapes from K-12 school math. Triangles appear to work, contrary to some earlier statements. Triangles of a single orientation take a large number of trials (i.e., the algorithm is slow). For triangles and squares it has been shown by Paul Bourke that they also fractalize with random orientation (3 random variables). I have constructed a pattern where no two shapes are the same (no congruency, 5 random variables) and the algorithm works there too.
There may be be some requirement on "compactness" of shapes but what it is isn't clear at this time. On the other hand, if "fractalize" allows use of any c value > 1, the quite sparse fractals one gets with c close to 1 may in fact allow any shape to be fractalized.
The shapes can have holes in them (e.g., rings).
"Gears" made by superimposing a 7-cycle sine wave around the edge of a circle are about the slowest-to-run case thus far studied. The power law for total trials versus number n of placed circles had an exponent of f=2.7 in this case, which is the highest I have thus far seen (indicating that the algorithm runs slowly). The use of polar coordinates to describe the shape relative to its placement point has considerable merit.
Usable values of c. Most work to date has used c values from about 1.2 to 1.4. My own studies strongly suggest that c=1.50 to 1.52 is the upper limit. It can be shown for circles-in-circle fractals that with c greater than about 1.51 it is not possible to place the first and second circles (both can't fit). The algorithm "dies" at high c values because of strong fluctuations -- the power law for total trials versus n starts to have oscillatory fluctuations on top of the main trend, which become stronger as c goes beyond about 1.4. It is thought that in these high-c cases the algorithm actually creates a situation in which there is no hole big enough for the next shape. In the high-c case there is a substantial random variation in how far the algorithm goes before quitting. "History" makes a difference.
The low-c case has been little studied. As c->1 the zeta function goes to infinity, so that in the low-c case one winds up placing larger and larger numbers of very tiny shapes. In the limit c->1 the fractal dimension approaches 2, i.e. the value for ordinary 2D Euclidean space.
Space-filling? The set of shapes is "space-filling" by construction if the algorithm never stops. Computational evidence to date is that it doesn't stop. So it is "computationally" space-filling. A proper and rigorous mathematical proof of this as n goes to infinity would require some very involved limit-taking. It is a serious math problem and has not yet been attempted.
Three dimensions. On 8/8/11 I received an image from Paul Bourke which indicates that a 3D version of the statistical geometry algorithm works. Go back to the links page for a separate page on this.
One dimension. This works well and may be the simplest case. Go back to the links page for a separate page on this. In June 2012 a detailed techical article on this appeared in the Fall-Winter issue of Hyperseeing -- the journal of ISAMA. Available from lulu.com.
Why does a power law for the areas do this? Studies of the dimensionless average gasket width
b(c,n) = (total gasket area)/(total gasket perimeter)*(diameter of next circle)
for circles show that b(c,n) drops rapidly with increasing c, and is almost independent of n, i.e., the "available space" for new placements (relative to gasket width) is almost independent of n. The quantity b(c,n) is not random and can be computed from various sums of powers of n^-c and n^-(c/2) (e.g., using zeta functions).
Holes in circle patterns. Evidence thus far (see separate item) shows that after n circles have been placed one has (n-1) "interior" holes (not touching the boundary) and (n-1) "edge" holes (touching the boundary). This is inferred from study of low-n examples and needs more study.
Workers. Paul Bourke (Univ. of Western Australia); his web site contains many examples. The Swiss engineer and computer scientist Dr. Goulu has also constructed some of these fractals.