The Menger Sponge, Complement and Associate

著者 Cleve Moler, January 15, 2022

10 ビュー (過去 30 日間) | 0 いいね | 2 コメント

A few months ago, I had never heard of Karl Menger or the cube-like fractal that he invented. Now I have this long blog post about the sponge, and an extension that I am calling its "associate".

Complements and associates
Code comes first
Level 0
Level 1
Level 2
Level 3
Ten levels
Associate
Level 2
Level 3
Level 4

Complements and associates

The complement of the Menger sponge fractal at a given level is all the material that is cut away to reach that level. The sponge associate is something I encountered while trying to compute the sponge complement.

Code comes first

I firmly believe that carefully written computer code is a means for people to communicate with each other, as well as control machines. Some of the images that I am about to present can be seen elsewhere on the Web, but I am most pleased with the code that produces them, so I will describe it first.

Here is the main routine, sponge . If you have been following this blog, you will have seen some of it before. At the command line, sponge expects only two input arguments, a nonnegative integer specifying the level and a boolean variable specifying the Menger sponge or its complement. The sponge is displayed with a dark shade of gold and the complement with a light shade. The function sponge is recursive and the recursive calls have more than two arguments.

Level zero terminates the recursion and is dealt with first. The level zero sponge is a solid cube. The level zero complement is empty and we just display the outline of a cube. Ultimately, all the output is produced by function calls cube(d,w,c), which displays a dark or light cube with half-width w centered at c = [x y z], so nothing but cubes of various sizes in various locations are displayed. Ordinarily the cube is merged with whatever is in the current figure, thus displaying the union of the two sets. A cla command clears the current display axis and thereby initiates a new set.

If the level is not zero, we reach the nested loops and the recursive calls. The variables x, y and z take on all possible combinations of -2, 0 and +2, so the innermost statements are executed 27 times. Now the key variable nz comes into play. It is the number of nonzeros in [x y z]. The vector [0 0 0] has zero nonzeros and is in the center of some small cube. Vectors like [2 0 0] and [0 -2 0] have one nonzero and are in the center of some face of that small cube. Vectors like [2 0 -2] with two nonzeros are in the middle of some edge and vectors like [-2 2 -2] with three nonzeros are at the corners. There are seven [x y z]'s with nz < 2 leaving 20 with nz >= 2. This provides the trisecting rule for generating the next level Menger sponge.

    type sponge

function sponge(m,s,d,w,c)
    % sponge(m,s)
    % m: level, 20^m cubes.
    % s: sponge, dark gold or complement, light gold.
    %
    % Resursive usage:
    % sponge(m,s,d,w,c)
    % d: dark or light.
    % w: half-width.
    % c: center.

    if nargin == 2
        init_fig(5)
        sponge(m,s,s,3,[0 0 0])
        
    elseif m == 0 && s
        cube(d,w,c)
        
    elseif m == 0
        cube([],w,c)
        
    else
        w = w/3;
        c = c/3;
        for x = [-2 0 2]
            for y = [-2 0 2]
                for z = [-2 0 2]
                    nz = nnz([x y z]);
                    if s && nz >= 2
                        sponge(m-1,s,d,w,c+[x y z])
                    elseif ~s && nz < 2
                        sponge(m-1,~s,d,w,c+[x y z])
                    end
                end
            end
        end
    end
end

Level 0

This is the level 0 sponge, a solid cube.

    cla
    sponge(0,true)

This is the level 0 complement. It is empty.

    cla
    sponge(0,false)

Level 1

Trisect level 0 into 3x3x3 = 27 smaller cubes. Delete the center cube and the center of each face. This is the level 1 sponge with 20 smaller cubes and seven holes.

    cla
    sponge(1,true)

This is the level 1 complement, the seven missing cubes.

    cla
    sponge(1,false)

If you could somehow put the level 1 sponge and the level 1 complement together again, you would recreate a slightly used, but full, cube.

    cla
    sponge(1,true)
    sponge(1,false)

Level 1 is as far as I need to go late last year in order to decorate my Season's Greetings.

Level 2

The level 2 sponge has 20^2 = 400 cubes. I got this far in level 2 for my first post about the Menger sponge.

    cla
    sponge(2,true)

The next figure has never appeared before in Cleve's Corner. I call it the level 2 partial complement.

    cla
    sponge(2,false)

Form the union of the level 2 partial complement and the level 1 complement to give the entire level 2 complement.

    sponge(1,false)

The union of the level 2 sponge and its complement is a full cube.

    sponge(2,true)

Level 3

The is the level 3 Menger sponge. It is made from 20^3 = 8000 small cubes. Its volume is less than half that of the original cube.

    cla
    sponge(3,true)

The is the level 3 partial complement.

    cla
    sponge(3,false)

Combine levels 1, 2 and 3 partial complements to produce the entire level 3 complement.

    sponge(2,false)
    sponge(1,false)

The union of the level 3 sponge and its complement is, again, full.

    sponge(3,true)

    format compact
    format short

Ten levels

I don't have enough time and my laptop doesn't have enough memory to go much beyond level 3, but if we could continue trisecting, the level 10 sponge would be made out of 20^10 = 10,240,000,000,000 very tiny cubes.

Level m would reduce the volume of the level 0 cube by a factor r.^m where

   r = (20/27)

r =
    0.7407

By level 10 the volume of the sponge would be only 5 percent of the original volume, and the remaining 95 percent would be in the complement.

    m = (0:10)';
    volumes = [r.^m 1-r.^m];

    fprintf('\n\n                 volume\n')
    fprintf('      level  sponge  complement\n')
    fprintf('%10d %8.3f %8.3f\n',[m volumes]')


                 volume
      level  sponge  complement
         0    1.000    0.000
         1    0.741    0.259
         2    0.549    0.451
         3    0.406    0.594
         4    0.301    0.699
         5    0.223    0.777
         6    0.165    0.835
         7    0.122    0.878
         8    0.091    0.909
         9    0.067    0.933
        10    0.050    0.950

    plot(m,volumes,'o-','linewidth',1.0)
    xlabel('level')
    ylabel('volume')
    legend({'sponge','complement'},'position',[.67 .47 .21 .08])

    close

Associate

A Web dictionary says that an associate is someone with limited or subordinate membership in an organization. We are all familiar with associate professors in academic organizations. I accidentally created these sponge associates when I was learning how to compute sponge complements. I liked the images, so I have kept them around.

The code that I now have for generating associates is almost the same as the code for generating sponges. Just count the number of zeros in a coordinate vector instead of the number of nonzeros.

    dbtype 28 sponge
    dbtype 28 associate

28                        nz = nnz([x y z]);

28                        nz = 3 - nnz([x y z]);

Level 2

At levels 0 and 1, sponges and associates construct the same objects. But at level 2 we have this fellow with 49 cubes.

    cla
    associate(2,true)

The associates have their own complements. The cube count at level m is 7^m for an associate and 20*7^(m-1) for its complement. This one at level 2 has 149 cubes.