A kinetic triangulation scheme for moving points in the plane

作者：Kaplan Haim; Rubin Natan^*; Sharir Micha

来源：Computational Geometry-Theory and Applications, 2011, 44(4): 191-205.

DOI：10.1016/j.comgeo.2010.11.001

• Triangulation
• Kinetic data structure
• Pseudo-triangulation
• Treaps

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(2)beta(s+2)(n) log(2) 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, beta(s+2)(q) = lambda(s+2)(q)/q, and lambda(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.

• 出版日期2011-5