14
$\begingroup$

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!

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – Timothy Sun
    Commented Oct 11, 2011 at 4:20
  • 1
    $\begingroup$ On the same page, it states "The current best bound is 30". The number 56 is for polygonization. $\endgroup$
    – Chao Xu
    Commented Oct 11, 2011 at 8:35
  • 3
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 11, 2011 at 11:53
  • 3
    $\begingroup$ 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)) $\endgroup$
    – Suresh Venkat
    Commented Oct 11, 2011 at 13:55
  • 2
    $\begingroup$ 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) $\endgroup$
    – Suresh Venkat
    Commented Oct 11, 2011 at 16:06

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Excellent point, Suresh! I did not think of this connection. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 11, 2011 at 20:08
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.