On kinetic Delaunay triangulations: a nearquadratic bound for unit speed motions
On kinetic Delaunay triangulations: a nearquadratic bound for unit speed motions

Natan Rubin , Jussieu Institute of Mathematics/Paris 6
Fine Hall 224
Let P be a collection of n points in the plane, each moving along some straight line and at unit speed. Three points of P form a Delaunay triangle if their circumscribing circle contains no further point of P. These triangles form the famous Delaunay triangulation, denoted by DT(P). We obtain an almost tight upper bound of O(n^{2+eps}), for any eps>0, on the maximum number of discrete changes that DT(P) experiences during this motion. Our analysis is cast in a purely topological setting; we only assume that (i) any four points can be cocircular at most three times, and (ii) no triple of points can be collinear more than twice. These assumptions hold for unit speed motions.