a 2d kinetic triangulation with near-quadratic topological changes
A triangulation of a set S of points in the plane is a subdivision of the convex hull of S into triangles whose vertices are points of S . Given a set S of n points in &Ropf; 3 , each moving independently, we wish to maintain a triangulation of S. The triangulation needs to be updated periodically as the points in S move, so the goal is to maintain a triangulation with small number of topological events, each being the insertion or deletion of an edge. We propose a kinetic data structure (KDS) that processes n 2 2 O(?log nlog log n ) topological events, with high probability, if the trajectories of input points are algebraic curves of fixed degree. Each topological event can be processed in O (log n ) time. This is the first known KDS for maintaining a triangulation that processes near-quadratic number of topological events, and almost matches the ?( n 2 ) lower bound, [1]. The number of topological events can be reduced to nk  2 O(?log klog log n ) if only K of the points are moving.
triangulation kinetic data structures random sampling