Random triangulations of planar points sets
Emo Welzl · 2006
Given a set S of n points in the plane, a triangulation is a maximal crossingfree geometric graph on S (in a geometric graph the edges are realized by straight line segments). Here we consider random triangulations, where “random ” refers to uniformly at random from the set of all triangulations of S. We are primarily interested in the degree sequences of such random triangulations.