2013/04/12 by Natan Rubin, Rubin, Natan
Computer Science · Engineering · #52C45 #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #F.2.2 #FOS: Computer and information sciences #G.2.1 #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1304.3671
openalex publication_date 2013/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let P be a collection of n points moving along pseudo-algebraic trajectories in the plane. One of the hardest open problems in combinatorial and computational geometry is to obtain a nearly quadratic upper bound, or at least a subcubic bound, on the maximum number of discrete changes that the Delaunay triangulation \DT(P) of P experiences during the motion of the points of P. In this paper we obtain an upper bound of O(n2+\eps), for any \eps>0, under the assumptions that (i) any four points can be co-circular at most twice, and (ii) either no triple of points can be collinear more than twice, or no ordered triple of points can be collinear more than once.