Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

TOPOLOGY

Previous Up Next

ITEM 113:

Although not new (cf Coxeter, Introduction to Geometry, 1st ed. p393), the following coloring number (chromatic number) may be useful to have around: 
N = [[(7 + sqrt(48 H + 1))/2]]
where N is the number of colors required to color any map on an object which has H holes (note: proof not valid for H = 0).

For example:

ITEM 114 (Schroeppel):

A most regular 7-coloring of the torus can be made by tiling the plane with the following repeating pattern of hexagons of 7 colors: 
 A A       C C       E E
A A A     C C C     E E E
 A A  F F  C C  A A  E E
     F F F     A A A
 B B  F F  D D  A A  F F
B B B     D D D     F F F
 B B  G G  D D  B B  F F
     G G G     B B B
 C C  G G  E E  B B  G G
C C C     E E E     G G G
 C C  A A  E E  C C  G G
     A A A     C C C
 D D  A A  F F  C C  A A
D D D     F F F     A A A
 D D  B B  F F  D D  A A
     B B B     D D D
 E E  B B  G G  D D  B B
E E E     G G G     B B B
 E E  C C  G G  E E  B B
     C C C     E E E
      C C       E E
Draw an area 7 unit cell parallelogram by connecting, say, the center B's in each of the four 
 B B
B B B 's.
 B B
Finally, join the opposite sides of the parallelogram to form a torus in the usual (Spacewar) fashion. QUESTION (Gosper): is there a toroidal heptahedron corresponding to this?

ITEM 115 (Gosper):

A spacefilling curve is a continuous map T -> X(T),Y(T), usually from the unit interval onto the unit square, often presented as the limit of a sequence of curves made by iteratively quadrisecting the unit square. Each member of the sequence is then 4 copies of its predecessor, connected in the shape of an inverted V, with the first member being a V which connects 0,0 to 1,0. The limiting map, X(T) and Y(T), can be computed instead by a simple, finite-state machine having 4 inputs (digits of T base 4), 4 outputs (one bit of X and one bit of Y), and 4 states (2 bits) of memory (the number modulo 2 of 0's and 3's seen in T).

Let T, X, and Y be written in binary as: 

T=.A B A B A B ...   X=.X X X X X X ...   Y=.Y Y Y Y Y Y ...
    1 1 2 2 3 3          1 2 3 4 5 6          1 2 3 4 5 6
ALGORITHM S: 
        C  <- 0                          ;# of 0's mod 4
         0

        C  <- 0                          ;# of 3's mod 4
         1

S1:     X  <- A  XOR C                   ;Ith bit of X
         I     I      NOT B
                           I

        Y  <- X  XOR B                   ;Ith bit of Y
         I     I      I

        C  <- C  XOR (NOT A  AND NOT B ) ;count 00's
         0     0           I          I

        C  <- C  XOR (A  AND B )         ;count 11's
         1     1       I      I

        GO S1


OLD                  NEW
C  C   A  B   X  Y   C  C
 0  1   I  I   I  I   0  1

0  0   0  0   0  0   1  0
0  0   0  1   0  1   0  0
0  0   1  0   1  1   0  0
0  0   1  1   1  0   0  1
0  1   0  0   1  1   1  1
0  1   0  1   0  1   0  1    This is the complete
0  1   1  0   0  0   0  1    state transition table.
0  1   1  1   1  0   0  0
1  0   0  0   0  0   0  0
1  0   0  1   1  0   1  0
1  0   1  0   1  1   1  0
1  0   1  1   0  1   1  1
1  1   0  0   1  1   0  1
1  1   0  1   1  0   1  1
1  1   1  0   0  0   1  1
1  1   1  1   0  1   1  0
To carry out either the forward or reverse map, label a set of columns as in the table above. Fill in whichever you know of AB or XY, with consecutive rows corresponding to consecutive 1's. Put 0 0 in the top position of the OLD CC column. Exactly one row of the above table will match the row you have written so far. Fill in the rest of the row. Copy the NEW CC entry to the OLD CC column in the next row. Again, only one row of the state table will match, and so forth. For example, the map 5/6 -> (1/2,1/2) (really .11010101... -> (.1000... ,.0111...)): 
OLD                  NEW
C  C   A  B   X  Y   C  C
 0  1   I  I   I  I   0  1

0  0   1  1   1  0   0  1
0  1   0  1   0  1   0  1
0  1   0  1   0  1   0  1
0  1   0  1   0  1   0  1
.  .   .  .   .  .   .  .
.  .   .  .   .  .   .  .
    =  5/6  1/2  1/2
We note that since this is a one-to-one map on bit strings, it is not a one-to-one map on real numbers. For instance, there are 2 ways to write 1/2, .1000... and .0111..., and thus 4 ways to write (1/2,1/2), giving 3 distinct inverses, 1/6, 1/2, and 5/6. Since the algorithm is finite state, X and Y are rational iff T is, e.g., 898/4369 -> (1/5,1/3). The parity number, (see SERIES section) and 1-(parity number) are the only reals satisfying X(T)=T, Y(T)=1. This is related to the fact that they have no 0's and 3's base 4, and along with 0, 1/2, and 1=.111..., are the only numbers preserved by the deletion of their even numbered bit positions.

Previous Up Next