# The number of triangulations of a set of $n$ planar points: Why so difficult?

After hearing Emo Welzl speak on the subject this summer, I know the number of of triangulations of a set of $n$ points in the plane is somewhere between about $\Omega(8.48^n)$ and $O(30^n)$. Apologies if I am out-of-date; updates welcomed.

I mentioned this in class, and wanted to follow up with brief, sage remarks to give students a sense for (a) why it has proved so difficult to nail down this quantity, and (b) why so many care to nail it down. I found I did not have adequate answers to illuminate either issue; so much for my sageness!

I'd appreciate your take on these admittedly vague questions. Thanks!

• According to Erik Demaine's polygonization page, the bound stated in the talk was $O(56^n)$, but I don't remember whether or not Emo Welzl stated that one could show a better bound using more careful analysis. For some reason, I have $O(35^n)$ in my head. Oct 11, 2011 at 4:20
• On the same page, it states "The current best bound is 30". The number 56 is for polygonization. Oct 11, 2011 at 8:35
• Perhaps it is worthwhile giving my own answers to my questions. Triangulations are formed by noncrossing segments. Understanding noncrossing-ness is difficult. That's (a). For (b), the pursuit is driven by trying to understand noncrossing. I think you will agree these answers are inadequate. Oct 11, 2011 at 11:53
• As a point of reference, doing the same thing for points in convex position is a homework exercise via Catalan numbers. This is because we can characterize non-crossingness in a nice way via balanced parentheses (giving credence to point (a)) Oct 11, 2011 at 13:55
• I'd lean towards saying that this problem is not directly related to the EDC. Mainly because a key issue is characterizing noncrossing pairs, and also because there's a much stronger topological rather than geometric flavor to this question (and we have circumstantial evidence that the EDC is intrinsically geometric) Oct 11, 2011 at 16:06

## 2 Answers

Here's one more "applied" reason why we care about triangulations. There's a body of work on mesh compression where the goal is to use as few bits per vertex as possible to encode a mesh (mainly to aid in storage and transmission). The particular base of the exponent in the number of triangulations of a planar point set provides an information-theoretic lower bound on the number of bits needed per vertex (specifically, $8.48^n$ triangulations means you need at least 8.48 bits per vertex). Such bounds can then be compared with actual mesh compression schemes to determine their efficacy.

• Excellent point, Suresh! I did not think of this connection. Oct 11, 2011 at 20:08

The lower bound had been slightly improved to $\Omega(8.65^n)$ (see arXiv here). I try to maintain up-to-date bounds to various variants of this problem in this webpage (sorry about this shameless self-advertisement).

I very much like your claim that the problem is difficult because "understanding noncrossing-ness is difficult". The $30^n$ bound (and some of the previous bounds) relies on a connection between the number of triangulations and the expected properties of a random triangulation (chosen uniformly from the set of all possible triangulations of the point set). This transforms the problem into studying expected properties of a random triangulation, which is difficult because the noncrossing-ness doesn't allow us to use the standard probabilistic tools (e.g., we cannot choose each edge with some probability $p$ because this might induce some crossings). So the non-crossing-ness forces us to develop new methods for studying random graphs.

• that's a nice website. Jan 9, 2012 at 17:00