Understanding McMullen's Upper Bound Theorem I'm a computer science student working on a paper regarding constrained delaunay triangulations. I have been searching for a proof regarding the upper bound for the number of triangles in a constrained delaunay triangulation with $n$ vertices and I managed to find this paper:
http://www.cs.ucdavis.edu/~amenta/pubs/HiDeeDel.pdf
It provides an upper bound on the number of triangles in a delaunay triangulation (I was looking for constrained) using McMullen's Upper Bound Theorem (http://www.ifor.math.ethz.ch/teaching/lectures/poly_comp_ss11/lecture7). The paper doesn't describe their technique for finding the upper bound from McMullen's theorem in depth, so I'm forced to figure it out for myself.
Here's the problem. I have almost no math and geometry background past vector calculus and probability (my strengths lie in discrete math and graph theory), so I can't understand what McMullen's theorem means. I have a hunch that it can be applied to arbitrary triangulations (not just DTs), but I'm not sure how I would go about showing this.
Additionally, I really only care about the 2-dimensional case.
 A: McMullen's upper bound theorem really doesn't say anything in the planar case. It becomes useful only for "triangulations" (i.e. a division into simplices) in higher-dimensional space. As you surmise, it applies to any triangulation.
First you must see the connection between triangulations and polytopes. Consider a triangulation in the plane. If you imagine it drawn on the surface of a balloon, then all the space "outside" the triangulation is just another face (I'll call it the outer face.) You can shrink down the outer face. It's always possible to "complete" the triangulation, adding extra edges if necessary, so that the outer face is also a triangle; then when you put it on a balloon, you have a polyhedron with triangular faces.
You can do this with higher-dimensional triangulations as well: Any triangulation in $d$-space, together with its outer face, is the set of faces of a $(d+1)$-dimensional polytope.
McMullen's Upper Bound Theorem gives the maximum number of $i$-faces a $d$-dimensional polytope with $n$ vertices can possibly have (an $i$-face is a face of dimension $i$, so 0-faces are vertices, 1-faces are edges, etc.) Since triangulations are polytopes, it also gives an upper bound on the number of $i$-faces in a triangulation with $n$ vertices. Say $f_i$ is the number of $i$-faces; then the theorem says
$$
f_i \leq \binom{n}{i+1} \quad \text{ if }  0 \leq i \leq \left\lfloor\frac{d-2}{2}\right\rfloor.
$$
The upper bounds on the number of $i$-faces with $i \geq \lfloor\frac{d}{2}\rfloor$ are then determined by the Dehn-Sommerville equations.
For a planar triangulation, we are concerned with a 3-dimensional polytope (aka polyhedron), so the Upper Bound Theorem just says $f_0 \leq n$,
i.e. a triangulation with $n$ vertices has at most $n$ vertices, which is not exactly helpful.
The Dehn-Sommerville equations then tell you that $3 f_2 = 2 f_1$ and $f_0 - f_1 + f_2 = 2$, from which you can conclude that the number of edges $f_1 = 3n - 6$ and the number of triangles $f_2 = 2n - 4$. Keep in mind that this is only after you complete the triangulation, if necessary, so that the outer face is also a triangle, and count the outer face as one of the faces in $f_2$.
McMullen's theorem also gives an explicit construction of a $d$-polytope with $n$ vertices which achieves the maximum number of $i$-faces, for every $i$: namely take any $n$ points on the curve $(t,t^2,t^3,\dotsc,t^d)$ for your vertices.
