Line tangents to four fat triangles

H. Brönnimann, O. Devillers, S. Lazard, and F. Sottile

    In the Autumn of 2003 and the Spring of 2004, we ran an experiment whose goal was to generated four-tupes of triangles at random, recording the number of common tangents. This was done by choosing 12 random integer points from a box [-10000, 10000]^3, which were the vertices of the triangles.

    In all, we generated 5 million four-tuples of triangles and used 17,356,277.53 seconds of CPU time. 1 million were on a DEC alpha computer at the University of Massachusetts at Amherst, and the remaining on 1.2GHz AMD boxes at the MSRI. Early in the experiment, it was noticed that only even numbers of common tangents were observed, and this has now been proven in our forthcominig paper.

Frequency
Number of tangents 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40
Observed Frequency 1515706 331443 646150 403679 637202 327159 358312 238913 253396 114046 80199 44870 27726 12426 5796 2016 813 111 30 3 4


Description of Computation
We ran this via a shell script, which looped 250,000 to 1,000,000 times on each of the different machines. This shell script calls a MAPLE program, passing the loop variable to it as a seed for the random number generator. The MAPLE program (numberOfLines.maple) generates the four triangles, and then calls a routine numberOfTransversals(Triangles,n), whose input is the four triangles, and a integer n (which is zero on the initial call). numberOfTransversals is a procedure in the file procedures.maple which computes the number of tangents, in a fail-safe manner. That is, while is assumes that the four triangles are in general position as described above, it also detects when they are not. When they are not, it wiggles (perturbs) the triangles, and calls numberOfTransversals on the perturbed triangles, and with the integer n+1. (If the number n+1 is greater than 4, it exits with a "fail", but that never occurred.) The program numberOfLines.maple updates a table recording the frequencies. This is reproduced above.