A Two-Dimensional Kinetic Triangulation with Near-Quadratic Topological Changes

Written with Pankaj Agarwal and Yusu Wang.

Discrete & Computational Geometry (SoCG'04 special issue), 36:573-592, 2006.

Also in Proc. 20th Annual ACM Symposium on Computational Geometry, pages 180-189, 2004.

Downloads: PDF, PS

Abstract: 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 R², 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^{O(sqrt{logn·loglogn})} 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²) lower bound. The number of topological events can be reduced to nk·2^{O(sqrt{logk·loglogn})} if only k of the points are moving.