random triangulations of planar point sets
Let S be a finite set of n +3 points in general position in the plane, with 3 extreme points and n interior points. We consider triangulations drawn uniformly at random from the set of all triangulations of S , and investigate the expected number, v i , of interior points of degree i in such a triangulation. We provide bounds that are linear in n on these numbers. In particular, n /43? v 3 ? (2 n +3)/5.Moreover, we relate these results to the question about the maximum and minimum possible number of triangulations in such a set S , and show that the number of triangulations of any set of n points in the plane is at most 43 n , thereby improving on a previous bound by Santos and Seidel.
random triangulations number of triangulations degree sequences crossing-free spanning trees counting crossing-free geometric graphs charging