<p>The lower bound had been slightly improved to $\Omega(8.65^n)$ (<a href="http://arxiv.org/abs/1012.5664">see arXiv here</a>). I try to maintain up-to-date bounds to various variants of this problem <a href="http://www.cs.tau.ac.il/~sheffera/counting/PlaneGraphs.html">in this webpage</a> (sorry about this shameless self-advertisement).</p>

<p>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. </p>

CC BY-SA 3.0
2012-01-09T17:00:57.983Z
that's a nice website.
Suresh Venkat
CC BY-SA 4.0
2024-12-09T21:02:10.043Z
Website moved here:  https://adamsheffer.wordpress.com/numbers-of-plane-graphs/
Igor Pak
CC BY-SA 3.0
2012-01-09T10:39:13.573Z
2012-01-09T10:39:13.573Z
Adam Sheffer
<p>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. </p>

CC BY-SA 3.0
2011-10-11T20:08:03.970Z
Excellent point, Suresh!  I did not think of this connection.
Joseph O'Rourke
CC BY-SA 3.0
2011-10-11T18:03:29.573Z
2011-10-11T18:03:29.573Z
Suresh Venkat
<p>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.</p>

<p>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 <em>care</em> to nail it down.  I found I did not have adequate answers
to illuminate either issue; so much for my sageness!</p>

<p>I'd appreciate your take on these admittedly vague questions.  Thanks!</p>

CC BY-SA 3.0
2011-10-11T04:20:46.337Z
According to [Erik Demaine's polygonization page](http://erikdemaine.org/polygonization/), 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.
Timothy Sun
CC BY-SA 3.0
2011-10-11T08:35:55.087Z
On the same page, it states "The current best bound is 30". The number 56 is for polygonization.
Chao Xu
CC BY-SA 3.0
2011-10-11T09:44:58.133Z
I need to be more careful. I just assumed the question dealt with polygonizations. >_>
Timothy Sun
CC BY-SA 3.0
2011-10-11T11:53:19.240Z
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.
Joseph O'Rourke
CC BY-SA 3.0
2011-10-11T13:55:55.873Z
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))
Suresh Venkat
CC BY-SA 3.0
2011-10-11T15:00:13.923Z
Is there any chance this problem is easier now that the [Erdos Distance Conjecture is (essentially) solved](http://blog.computationalcomplexity.org/2010/11/erdos-distance-problem-solved.html)?  Idea being: there are strictly fewer "inequivalent classes of points in general position" we need to consider for possible triangulation, so it is now possible to decrease the upper bound.  If so, it would connect triangulation to the difficulty of a longstanding open problem in mathematics.
Aaron Sterling
CC BY-SA 3.0
2011-10-11T16:06:07.177Z
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)
Suresh Venkat
CC BY-SA 3.0
2011-10-11T19:51:15.747Z
One interesting implication of the asymptotic difference between the number of curves passing through a given set of points and the number of non-crossing curves passing through them is that even though there is an $\Omega(n\log n)$ lower bound for finding the convex hull of a set of points, the convex hull of a simple polygon can be found in linear time. Perhaps improving the upper bound in your question will give better constants in the running time of the convex hull algorithm?
Vinayak Pathak
<co.combinatorics><cg.comp-geom>
The number of triangulations of a set of $n$ planar points: Why so difficult?
Joseph O'Rourke
# The number of triangulations of a set of $n$ planar points: Why so difficult?

(Asked by: username_0 on 2011-10-11)

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!

**Tags:** co.combinatorics, cg.comp-geom

> **Comments:**
> **username_1**: According to [Erik Demaine's polygonization page](http://erikdemaine.org/polygonization/), 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.  
> **username_2**: On the same page, it states "The current best bound is 30". The number 56 is for polygonization.  
> **username_1**: I need to be more careful. I just assumed the question dealt with polygonizations. >_>  
> **username_0**: 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.  
> **username_3**: 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))  
> **username_4**: Is there any chance this problem is easier now that the [Erdos Distance Conjecture is (essentially) solved](http://blog.computationalcomplexity.org/2010/11/erdos-distance-problem-solved.html)?  Idea being: there are strictly fewer "inequivalent classes of points in general position" we need to consider for possible triangulation, so it is now possible to decrease the upper bound.  If so, it would connect triangulation to the difficulty of a longstanding open problem in mathematics.  
> **username_3**: 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)  
> **username_5**: One interesting implication of the asymptotic difference between the number of curves passing through a given set of points and the number of non-crossing curves passing through them is that even though there is an $\Omega(n\log n)$ lower bound for finding the convex hull of a set of points, the convex hull of a simple polygon can be found in linear time. Perhaps improving the upper bound in your question will give better constants in the running time of the convex hull algorithm?  

---

## 2 answers

### Answer by username_3 on 2011-10-11. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_0**: Excellent point, Suresh!  I did not think of this connection.  

---

### Answer by username_6 on 2012-01-09. Score: 8

The lower bound had been slightly improved to $\Omega(8.65^n)$ ([see arXiv here](http://arxiv.org/abs/1012.5664)). I try to maintain up-to-date bounds to various variants of this problem [in this webpage](http://www.cs.tau.ac.il/~sheffera/counting/PlaneGraphs.html) (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.

> **Comments:**
> **username_3**: that's a nice website.  
> **username_7**: Website moved here:  https://adamsheffer.wordpress.com/numbers-of-plane-graphs/  

---

