Voronoi diagrams of rigidly moving sets of points
Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg · Information Processing Letters · 1992
Consider k sets each consisting of n points in the plane, with each set allowed to move rigidly according to some continuous function of time. A paper by Aonuma, Imai, Imai, and Tokuyama shows an upper bound of O(n3k4log∗n) on the number of combinatorial changes to the Voronoi diagram of the kn points over all time. We present a bound of O(n2k2λs(k)) for s fixed s, thus improving their result by slightly more than a factor of kn.