on degrees in random triangulations of point sets
We study the expected number of interior vertices of degree i in a triangulation of a point set S , drawn uniformly at random from the set of all triangulations of S , and derive various bounds and inequalities for these expected values. One of our main results is: For any set S of N points in general position, and for any fixed i , the expected number of vertices of degree i in a random triangulation is at least ? iN , for some fixed positive constant ? i (assuming that N > i and that at least some fixed fraction of the points are interior). We also present a new application for these expected values, using upper bounds on the expected number of interior vertices of degree 3 to get a new lower bound, ?(2.4317 N ), for the minimal number of triangulations any N -element planar point set in general position must have. This improves the previously best known lower bound of ?(2.33 N ).
random triangulations plane graphs degree sequences number of triangulatons counting crossing-free geometric graphs charging