INCREMENTAL TOPOLOGICAL FLIPPING WORKS FOR REGULAR TRIANGULATIONS

A set of n weighted points in general position in R(d) defines a uniqu e regular triangulation. This paper proves that if the points are adde d one by one, then flipping in a topological order will succeed in con structing this triangulation. If, in addition, the points are added in a random sequence and the history of the flips is used for locating t he next point, then the algorithm takes expected time at most O(n log n + n(inverted left perpendicular d/2 inverted right perpendicular)). Under the assumption that the points and weights are independently and identically distributed, the expected running time is between proport ional to and a factor log n more than the expected size of the regular triangulation. The expectation is over choosing the points and over i ndependent coin-flips performed by the algorithm.