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.