[Mittagsseminar TI] Seminar tomorrow Thursday, 16:15 Uhr, N. Rubin on kinetic Delaunay triangulations
Special "MIttagsseminar":
Thursday, June 27, 16:15-17:30 Uhr, Seminarraum 005, Takustraße 9
Natan Rubin, Freie Universität Berlin
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. We obtain an almost tight upper bound of O(n^{2+epsilon}), for any
epsilon>0, on the maximum number of discrete changes that the Delaunay triangulation of P
experiences during this motion. Our analysis is cast in a purely combinatorial setting,
where 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.
--
G"unter Rote
