Incremental topological flipping works for regular triangulations

A set ofn weighted points in general position in ^d defines a unique regular triangulation. This paper proves that if the points are added one by one, then flipping in a topological order will succeed in constructing this triangulation. If, in addition, the points are added in a random sequence and the history of the flips is used for locating the next point, then the algorithm takes expected time at mostO(nlogn+n ^d/2]). Under the assumption that the points and weights are independently and identically distributed, the expected running time is between proportional to and a factor logn more than the expected size of the regular triangulation. The expectation is over choosing the points and over independent coin-flips performed by the algorithm.The research of both authors was supported by the National Science Foundation under Grant CCR-8921421 and the research by the first author was also supported under the Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation.