2014/04/18 by Pankaj K. Agarwal, Agarwal, Pankaj K., Haim Kaplan +5
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #I.3.5 #Metric Geometry (math.MG) #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1404.4851
openalex publication_date 2014/04/18 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Let P be a set of n points and Q a convex k-gon in \mathbb R2. We analyze in detail the topological (or discrete) changes in the structure of the Voronoi diagram and the Delaunay triangulation of P, under the convex distance function defined by Q, as the points of P move along prespecified continuous trajectories. Assuming that each point of P moves along an algebraic trajectory of bounded degree, we establish an upper bound of O(k4nλr(n)) on the number of topological changes experienced by the diagrams throughout the motion; here λr(n) is the maximum length of an (n,r)-Davenport-Schinzel sequence, and r is a constant depending on the algebraic degree of the motion of the points. Finally, we describe an algorithm for efficiently maintaining the above structures, using the kinetic data structure (KDS) framework.