Random triangulations of planar point sets
Micha Sharir, Emo Welzl · 2006
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 all triangulations of S, and investigate the expected number, ˆvi, 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 ≤ ˆv3 ≤ (2n + 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.