On kinetic Delaunay triangulations: a near-quadratic 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 co-circular at most three times, and (ii) no triple of points can be collinear more than twice. These assumptions hold for unit speed motions.