*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday October 24th, 4:30 in Fine Hall 224. Speaker: Natan Rubin (Jussieu Institute of Mathematics/Paris 6) Title: On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions 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. ----------- Next week: Fall recess. Week after: Krystal Guo. Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)