An Implementation of the Enumeration of Regular Triangulations (by Tomonari Masada Tel. 0423-35-1073) Compile: When you need a program for the enumeration of regular triangulations for point configurations, compile the source with example%gcc -O2 -o regtri regtri.c /usr/local/misc/lib/libgmp.a after checking the absence of the line '#define EXPERIMENT'. When you need a program for the experimentation (i.e., enumerations for randomly generated configurations), compile the source by the same manner after modifying the line '/*#define EXPERIMENT*/' into '#define EXPERIMENT', or, if such a line does not exist, by inserting the line '#define EXPERIMENT' on the head of the code. Usage (Non-experimental Case): If you initiate the enumeration from the root (i.e., initiate the enumeration normally), run the program in the following manner: example%regtri [input file] [output file] If you initiate the enumeration from some intermediate node, run the program in the following manner: example%regtri [input file] [output file] [the number of the intermediate regular triangulation] [data file] See the examples below. Usage (Experimental Case): If you do the experimentations, run the program in the following manner: example%regtri [the value of 'd'] [the value of 'n'] [output file] The values of 'd' and 'n' must be more than or equal to 2. Then, the program do the enumerations for 20 random configurations. See the examples below. Examples: An example of input files: 7 12 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 The first row indicates the values of 'd' and 'n' in this order. The other rows are those of the matrix whose columns indicates the coordinates of the input points. In this case, the input configuration is the set of 7 points. An example of data file (for the enumerations initiated from an intermedtate node): [S]< 1 2 3 6 9 12> [S]< 1 2 5 6 9 12> [S]< 1 2 5 8 9 12> [S]< 1 2 5 8 11 12> [S]< 1 4 5 6 9 12> [S]< 1 4 5 8 9 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 11 12> [S]< 1 4 7 10 11 12> *** [S]< 1 2 3 4 7 10> [S]< 2 3 4 6 7 10> [S]< 2 3 6 7 9 10> [S]< 2 3 6 9 10 12> [S]< 2 4 5 6 7 10> [S]< 2 5 6 7 9 10> [S]< 2 5 6 9 10 12> [S]< 2 5 7 8 9 10> [S]< 2 5 8 9 10 12> [S]< 2 5 8 10 11 12> Data file must include the data of the root regular triangulation and of the intermediate regular triangularion. The first ten lines shows the regular triangulation standing for the root node. Each line led by the symbols '[S]' ('S' is an abbreviation of 'simplex') indicates a simplex by the tuple of indices. The last ten lines shows the regular triangulation from where the enumeration re-starts. Two triangulations must be separated by the line '***'. An example of output (Non-experimental case): >>>: >>>: Initial triangulation. [S]< 1 2 3 4 9 12> [S]< 1 2 4 8 9 12> [S]< 1 2 4 8 10 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 10 12> [S]< 2 3 4 6 9 12> [S]< 2 4 5 6 8 12> [S]< 2 4 5 8 11 12> [S]< 2 4 6 8 9 12> [S]< 2 4 8 10 11 12> ***--- To reach the optimum... [S]< 1 2 3 6 9 12> [S]< 1 2 4 6 9 12> [S]< 1 2 4 8 9 12> [S]< 1 2 4 8 10 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 10 12> [S]< 2 4 5 6 8 12> [S]< 2 4 5 8 11 12> [S]< 2 4 6 8 9 12> [S]< 2 4 8 10 11 12> ***--- To reach the optimum... [S]< 1 2 3 6 9 12> [S]< 1 2 4 6 9 12> [S]< 1 2 4 8 9 12> [S]< 1 2 4 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 10 12> [S]< 1 4 8 10 11 12> [S]< 2 4 5 6 8 12> [S]< 2 4 5 8 11 12> [S]< 2 4 6 8 9 12> ***--- To reach the optimum... [S]< 1 2 3 6 9 12> [S]< 1 2 4 6 8 12> [S]< 1 2 4 8 11 12> [S]< 1 2 6 8 9 12> [S]< 1 4 6 8 9 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 10 12> [S]< 1 4 8 10 11 12> [S]< 2 4 5 6 8 12> [S]< 2 4 5 8 11 12> ***--- To reach the optimum... [S]< 1 2 3 6 9 12> [S]< 1 2 5 6 8 12> [S]< 1 2 5 8 11 12> [S]< 1 2 6 8 9 12> [S]< 1 4 5 6 8 12> [S]< 1 4 5 8 11 12> [S]< 1 4 6 8 9 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 10 12> [S]< 1 4 8 10 11 12> ***--- To reach the optimum... [S]< 1 2 3 6 9 12> [S]< 1 2 5 6 9 12> [S]< 1 2 5 8 9 12> [S]< 1 2 5 8 11 12> [S]< 1 4 5 6 9 12> [S]< 1 4 5 8 9 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 10 12> [S]< 1 4 8 10 11 12> ***--- To reach the optimum... [S]< 1 2 3 6 9 12> [S]< 1 2 5 6 9 12> [S]< 1 2 5 8 9 12> [S]< 1 2 5 8 11 12> [S]< 1 4 5 6 9 12> [S]< 1 4 5 8 9 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 11 12> [S]< 1 4 7 10 11 12> ****** [1] Optimal triangulation ****** [S]< 1 2 3 6 9 12> [S]< 1 2 5 6 9 12> [S]< 1 2 5 8 9 12> [S]< 1 2 5 8 11 12> [S]< 1 4 5 6 9 12> [S]< 1 4 5 8 9 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 11 12> [S]< 1 4 7 10 11 12> ***------ [1]th adjacent triangulation. ****** [2] Regular Triangulation ****** [S]< 1 2 3 5 9 12> [S]< 1 2 5 8 9 12> [S]< 1 2 5 8 11 12> [S]< 1 3 5 6 9 12> [S]< 1 4 5 6 9 12> [S]< 1 4 5 8 9 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 11 12> [S]< 1 4 7 10 11 12> ***------ [1]th adjacent triangulation. ***------ [2]th adjacent triangulation. ****** [3] Regular Triangulation ****** [S]< 1 2 3 5 8 12> [S]< 1 2 5 8 11 12> [S]< 1 3 5 6 9 12> [S]< 1 3 5 8 9 12> [S]< 1 4 5 6 9 12> [S]< 1 4 5 8 9 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 11 12> [S]< 1 4 7 10 11 12> ***------ [1]th adjacent triangulation. ***------ [2]th adjacent triangulation. ****** [4] Regular Triangulation ****** [S]< 1 2 3 5 8 11> [S]< 1 3 5 6 9 12> [S]< 1 3 5 8 9 12> [S]< 1 3 5 8 11 12> [S]< 1 4 5 6 9 12> [S]< 1 4 5 8 9 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 11 12> [S]< 1 4 7 10 11 12> ***------ [1]th adjacent triangulation. ***------ [2]th adjacent triangulation. ****** [5] Regular Triangulation ****** [S]< 1 2 3 5 8 11> [S]< 1 3 4 5 9 12> [S]< 1 3 5 8 9 12> [S]< 1 3 5 8 11 12> [S]< 1 4 5 8 9 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 11 12> [S]< 1 4 7 10 11 12> [S]< 3 4 5 6 9 12> ***------ [1]th adjacent triangulation. ***------ [2]th adjacent triangulation. ***------ [3]th adjacent triangulation. ****** [6] Regular Triangulation ****** [S]< 1 2 3 5 8 11> [S]< 1 3 4 5 8 12> [S]< 1 3 4 8 9 12> [S]< 1 3 5 8 11 12> [S]< 1 4 5 8 11 12> [S]< 1 4 7 8 9 12> [S]< 1 4 7 8 11 12> [S]< 1 4 7 10 11 12> [S]< 3 4 5 6 9 12> [S]< 3 4 5 8 9 12> The line '****** [x] Regular Triangulation ******' leads the x-th simplex. The number 'x' between brackets is used for the execution of the enumeration from the intermediate regular triangulation. An example of output (Experimental case): 16 regular trinagulations. [time]: 23115742 14 regular trinagulations. [time]: 17165980 14 regular trinagulations. [time]: 16865992 14 regular trinagulations. [time]: 18049278 14 regular trinagulations. [time]: 18432596 14 regular trinagulations. [time]: 18265936 14 regular trinagulations. [time]: 16799328 14 regular trinagulations. [time]: 19099236 14 regular trinagulations. [time]: 17632628 15 regular trinagulations. [time]: 19299228 14 regular trinagulations. [time]: 17649294 14 regular trinagulations. [time]: 18149274 14 regular trinagulations. [time]: 17499300 15 regular trinagulations. [time]: 19582550 15 regular trinagulations. [time]: 20149194 15 regular trinagulations. [time]: 21299148 16 regular trinagulations. [time]: 22799088 14 regular trinagulations. [time]: 18215938 15 regular trinagulations. [time]: 19782542 15 regular trinagulations. [time]: 20249190 Total: 380101462 msc. Each pair of two lines shows the number of regular triangulations and the time necessary for the enumeration. The total execution time is shown in the last row. An example of execution: example%regtri datac.dat datac.res --- Do the enumeration for the configuration saved in the file 'datac.dat', and store the results in the file 'datac.res'. example%regtri datac.dat datac.res 100 datac.tri --- Do the enumeration for the configuration saved in the file 'datac.dat' from the 100th regular triangulation saved in the file 'datac.tri' (the format is shown above), and store the results in the file 'datac.res'. example%regtri 3 6 exp3-6.res --- Suppose the sourse is compiled with the line '#define EXPERIMENT'. Then, the experiment with 6 points in the 2 (= 3 - 1) dimensional affine space starts. That is, the program executes enumerations for 20 random configurations of 6 points in the plane. The results is stored in 'exp3-6.res'.