Counting Triangulations - Olympics

The following table contains minimizing and maximizing examples for the number of triangulations of a set of points in the plane for fixed cardinality. Also available below are examples of regular grids, and the (currently) largest set of randomly chosen points for which the exact number of triangulations is known.

Note that all the sets (of course except the grids) are in general position, i.e. no three points lie on a common line. The method used to count the number of triangulations for these examples is the recently developed path-method, see my publication about it. (In addition there exist two Master Thesis by B. Erkinger and J. Gimpl (in german) who implemented and tested the algorithms.) You can also count triangulations of sets of points via our e-mail service. To ensure the correctness of the results all large sets were counted twice using different orientations. Though this does of course not affect the number of triangulations it leads to completely different (number of) paths in the method we used. It is thus very unlikely that the same overall result (sum of products of sub-parts produced by the paths) would arise if for some reason the method/implementation is incorrect.

Best examples (so far) for up to 20 vertices

Number of Vertices	Minimizing		Convex Set	Maximizing
	lower bound	best example		best example	upper bound
Minimum and maximum number of triangulations of point sets in the plane (points in general position, i.e. no three points are on a common line)
3	1	1 triangle, file	1	1 convex(3), file	1
4	1	1 triangle with inner point, file	2	2 convex(4), file	2
5	2	2 double circle(5), file	5	5 convex(5), file	5
6	4	4 double circle(6), file	14	14 convex(6), file	14
7	11	11 double circle(7), file	42	42 convex(7), file	42
8	30	30 double circle(8), file	132	150 swrpp(8), file	150
9	89	89 double circle(9), file	429	780 swrpp(9), file	780
10	250	250 double circle(10), file	1 430	4 550 swrpp(10), file	4 550
11	776	776 double circle(11), file	4 862	26 888 special set, file	26 888
12	1 026	2 236 double circle(12), file	16 796	168 942 special set, file	824 565
13	1 802	7 147 double circle(13), file	58 786	1 098 904 special set, file	26 516 274
14	2 828	20 979 double circle(14), file	208 012	7 281 984 special set, file	8.8 E 08
15	6 423	68 448 double circle(15), file	742 900	49 789 428 special set, file	3.0 E 10
16	14 560	203 748 double circle(16), file	2 674 440	342 305 320 special set, file	1.2 E 12
17	35 015	674 949 double circle(17), file	9 694 845	2 410 168 190 special set, file	4.1 E 13
18	81 947	2 031 054 double circle(18), file	35 357 670	17 309 628 327 special set, file	1.6 E 15
19	200 206	6 807 382 double circle(19), file	129 644 790	124 724 759 130 special set, file	6.0 E 16
20	602 176	20 662 980 double circle(20), file	477 638 700	918 462 742 512 special set, file	2.3 E 18

Note that we do not consider triangulations as graphs but as geometric objects, i.e. not only topology but geometry counts!

The given bounds are computed using the results of the following papers:
Lower bounds: O. Aichholzer, F. Hurtado, M. Noy: On the Number of Triangulations Every Planar Point Set Must Have, in Proc. 13th Annual Canadian Conference on Computational Geometry CCCG 2001, pages 13-16, Waterloo, Ontario, Canada, 2001
Upper bounds: F. Santos, R. Seidel: A better upper bound on the number of triangulations of a planar point set. J. Combin. Theory Ser. A, 102:186-193, 2003.

Largest set of (almost) randomly chosen points

This is the currently largest set of (almost) randomly chosen points for which the exact number of triangulations is known - try to count them with your favourit method! (Randomly here means that we took 32 European cities - try to figure out which ones!!)

The set has 32 points and 11 083 133 879 152 184 837 triangulations!

And here is a 'really' random set of 30 points with 65 095 805 477 698 136 triangulations!

Regular Grids

Here are some examples for regular nxm-grids for which we computed the exact number of triangulations. You can use these example to check if your favourit counting method can handle sets with collinear points or sets of size larger than 40 .... (More sets to come!)

Recently an interesting paper with a lot of nice results about the number of triangulations on grids appeared, so these computational results are not that interesting anymore (but at least the theoretical results confirmed our computations ;). See Volker Kaibel and Günter M. Ziegler, 'Counting Lattice Triangulations', in: Surveys in Combinatorics 2003, C. D. Wensley (ed.), London Math. Society Lecture Notes Series 307, Cambridge University Press, 2003, 277-307.

Example: the 3x15 Grid

Size of Grid	Points	Number of Triangulations
3 x 2	6	6
3 x 3	9	64
3 x 4	12	852
3 x 5	15	12 170
3 x 6	18	182 132
3 x 7	21	2 801 708
3 x 8	24	43 936 824
3 x 9	27	698 607 816
3 x 10	30	11 224 598 424
3 x 11	33	181 815 529 916
3 x 12	36	2 964 167 665 340
3 x 13	39	48 580 814 410 080
3 x 14	42	799 696 199 314 500
3 x 15	45	13 212 398 835 196 240
3 x 16	48	218 976 668 040 908 248
4 x 4	16	46 456
4 x 5	20	2 822 648
4 x 6	24	182 881 520
4 x 7	28	12 244 184 472
4 x 8	32	839 660 660 268
4 x 9	36	58 591 381 296 256
4 x 10	40	4 140 106 747 178 292
4 x 11	44	295 372 308 876 234 428
5 x 5	25	736 983 568
5 x 6	30	208 902 766 788
5 x 7	35	61 756 221 742 966
5 x 8	40	18 792 896 208 387 012
5 x 9	45	5 831 528 022 482 629 710
6 x 6	36	260 420 548 144 996
6 x 7	42	341 816 489 625 522 032