נתן רובין

We present a simple randomized scheme for triangulating a set P of n points in the plane, and construct a kinetic data structure which maintains the triangulation as the points of P move continuously along piecewise algebraic trajectories of constant description complexity. Our triangulation scheme experiences an expected number of O(n²β_s+2(n)log ²n) discrete changes, and handles them in a manner that satisfies all the standard requirements from a kinetic data structure: compactness, efficiency, locality and responsiveness. Here s is the maximum number of times at which any specific triple of points of P can become collinear, β_s+2(q)=λ _s+2 (q)/q, and λs+2(q) is the maximum length of Davenport-Schinzel sequences of order s+2 on q symbols. Thus, compared to the previous solution of Agarwal, Wang and Yu (2006) [4], we achieve a (slightly) improved bound on the number of discrete changes in the triangulation. In addition, we believe that our scheme is conceptually simpler, and easier to implement and analyze.